KMP 알고리즘

Overview

 

문자열 매칭은 여러 곳곳에서 흔하게 사용되는 알고리즘 중의 하나입니다. 당장에 브라우저에서 command + f 나 ctrl + f를 눌렀을때 나타나는 검색 바에서도 문자열 매칭을 통해 찾고자하는 문자열의 위치를 알려줍니다. 

 

가장 단순한 문자열 매칭 방법은 해당 페이지에 있는 모든 문자열에 대해서 찾고자 하는 문자열을 일일이 대입하는 방식일 것입니다. 전체 문자열의 길이를 $n$, 찾고자 하는 문자열의 길이를 $m$이라고 하면 $O(mn)$ 의 시간이 소요되게 될 것입니다. 이는 문자열의 길이가 굉장히 긴 경우에는 심각한 비효율성을 초래하기 때문에 개선의 필요성이 있으며, 

이를 효율적으로 개선한 방법 중의 하나 ( $ O(m+n) $ 의 시간복잡도를 가지고 있음 )가 이제 소개할 KMP알고리즘 입니다.

 

Definition

 

KMP 알고리즘은 Knuth, Moris, Pratt 이 세 사람이 만들었다고 해서 이들의 이니셜을 따 KMP 알고리즘이라는 이름을 갖게 되었습니다. 이 알고리즘의 핵심은 패턴의 각 위치에 대해 매칭에 실패했을 때, 돌아갈 곳을 알려주는 일차원 배열을 준비하고 이를 이용해 텍스트 문자열을 훑어 나가는 것입니다.  즉 "검색 과정에서 얻는 정보를 버리지 않고 잘 활용"해서 검색의 효율을 높이는 것입니다.

 

이를 위해서는 먼저 접두사, 접미사, Pi 배열에 대해 간단한 이해가 필요합니다.

 

1. 접두사(prefix) : 문자열의 맨 앞쪽부터 시작하는 부분을 의미합니다. (e.g "cat" 에서 "c", "ca", "cat")

2. 접미사(suffix) : 문자열의 맨 뒤쪽부터 시작하는 부분을 의미합니다. (e.g "cat" 에서 "t", "at", "cat")

3. Pi 배열 : KMP알고리즘에서 가장 핵심적인 역할을 하는 부분으로서, 접두사와 접미사가 일치하는 부분문자열 중에서 가장 긴 것의 길이를 의미합니다. (부분문자열은 주어진 문자열의 0~i까지의 문자열을 의미)

* 단 부분문자열의 길이는 전체가 될 수 없습니다.

 

Pi 배열은 이와 같이 접두사와 접미사가 일치하는 부분들을 저장함으로써 문자열 매칭에 실패했을 때, 혹은 매칭에 성공하고, 다음 매칭을 찾으려 할 때 단서를 제공합니다. 즉, 불필요한 비교를 최소화 할 수 있는 간단하지만 효율적인 도구를 제공하는 것이라고 할 수 있는 것이죠.

 

예를 들어 문자열 "ABCDABCDABCDABCDX"에서 문자열 "ABCDABCDX"를 찾는다고 하면, 

맨 처음 비교에서 "A"와 "X"가 불일치하지만, 부분문자열에서 접두사 "ABCD"와 접미사 "ABCD"가 서로 일치하기 때문에, 바로 그 위치로 건너 뛰어서 "ABCD"부터 비교할 수 있는 것입니다. 

A B C D A B C D A B ....	A B C D A B C D A B ....
A B C D A B C D X	.   .   .   . A B C D A B C D X

 

Code

 

KMP알고리즘의 아이디어를 살펴보았으니, 코드 구현을 통해 해당 알고리즘을 본격적으로 살펴보도록 하겠습니다. 

코드는 백준 1786번: 찾기 문제를 해결했던 코드입니다. 

 

코드는 크게 2가지 부분으로 구성되어 있습니다. 

문자열에 대해서 모든 부분 문자열에 대한 pi배열을 구하는 getPi함수와, pi 배열을 이용해서 문자열을 매칭하는 kmp함수인데, 각 부분에 대해서 간단하게 설명하도록 하겠습니다,

 

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>

using namespace std;

// get prefix & suffic arr
vector<int> getPi(string str) {
    int len = (int)str.size(), j=0;
    vector<int> pi(len, 0);
    for(int i=1; i<len;i++){
        while(j>0 && str[i] != str[j]) j = pi[j-1];
        if(str[i] == str[j]) pi[i] = ++j;
    }
    return pi;
}

// kmp algorithm
vector<int> kmp(string s, string p) {
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j=0;
    for(int i=0;i<n;i++){
        while(j>0 && s[i] != p[i]) j = pi[j-1];
        if(s[i] == p[i]) {
            if(j == m-1) {
                ans.push_back(i-m+1);
                j = pi[j];
            } else {
                j++;
            }
        }
    }
    return ans;
}

int main() {
    string s, p;
    getline(cin, s);
    getline(cin, p);

    auto matched = kmp(s, p);
    printf("%d\n", (int)matched.size());
    for(auto i: matched)
        printf("%d", i+1);

    return 0;
}

 

1. getPi 함수

 

getPi함수의 코드는 어떻게 보면 머리가 아픈 구조를 띄고 있는 것 같지만, pi 배열의 원리를 생각하여 접근하면 비교적 쉽게 이해할 수 있습니다. '접두사와 접미사가 일치하는 최대의 길이를 구하는 것' 이 원리에 집중해서 이해하셔야 합니다. 

 

헷갈리기 쉬워 짚고 넘어가야 하는 부분이 있다면, For Loop을 통해 i를 문자열 길이만큼 loop하는데, 우리가 구해야 하는 것은 매 loop 마다 0~i 까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이를 저장하는 것입니다. (사실 제가 헷갈렸음) 예를 들어 i=2라면 0~2 까지의 부분 문자열 중에서 접두사와 접미사가 일치하는 최대 길이를 찾는 것이죠

 

우선 부분 문자열의 길이가 1인 경우에는 접두사와 접미사가 당연히 일치하지만, 접두사, 접미사와 부분 문자열의 길이가 같으면 탐색에 의미가 없으므로, 0으로 초기화 해줍니다.

 

그 후, i가 증가할 때마다 다음과 같은 과정을 거칩니다. ( j는 이전 loop에서 접두사의 위치 바로 다음 위치를 가리키고 있는 변수입니다.) 

 

- 만약 j번째 문자와 i번째 문자가 같은 경우, 이전 접두사+문자 == 이전 접미사+문자 이므로 pi[i] = ++j가 됩니다.

- 만약 두 문자가 다른 경우에는,  j = pi[j-1]로 설정해줍니다. 이것은 KMP알고리즘의 원리를 getPi함수를 구현하는데에도 사용하여 시간을 절약한 부분이라고 할 수 있습니다. j번째 문자가 i번째 문자와 일치하지 않는 경우에, 그전에 최대로 일치했던 부분 문자열을 찾아서 다시 그 부분의 j와 i를 비교하고 또 다르면 그전에 최대로 일치했던 부분 문자열을 찾아서 다시 그 부분의 j와 i를 비교하는 방식인 것이죠. 결국 다 틀린 경우에는 pi가 0으로 바뀌게 되는 것입니다.

 

2. kmp 함수

 

kmp함수는 위의 getPi함수를 이해하셨다면 핵심 원리는 완전히 동일한 함수입니다. 

우선 찾고자 하는 함수의 pi배열을 getPi함수를 통해 얻어줍니다. 

그 후에 전체 문자열의 길이(찾고자 하는 문자열이 들어있는 문자열의 길이를 의미)만큼 For Loop을 돌면서 다음 과정을 반복합니다. p를 찾고자 하는 문자열, s를 대상이 되는 전체 문자열이라 하겠습니다.

 

- s[i] == p[j]인 경우 : j의 위치가 찾고자 하는 문자열의 길이와 같은 경우에 문자열 매칭이 성공한 것이므로 위치를 반환합니다. 그렇지 않은 경우에는, j의 위치를 한칸 다음으로 옮겨줍니다. (해당 위치까지 일치했다는 의미)

 

- s[i] != p[j]인 경우 : 이 부분이 KMP알고리즘의 핵심 부분입니다. 일치하지 않았을 경우에, 다시 처음부터 비교하는 것이 아니라, j 에서의 pi배열을 이용해서 중간 단계를 건너뛴 탐색을 수행하게 되는 것입니다.

 

예를 들어 "ABCDABCD"라는 문자열과 "ABCDABCW"라는 문자열을 비교할 때의 과정을 살펴보겠습니다. 

첫번째 두 줄에서 마지막 한 글자가 일치하지 않지만, 아래쪽의 문자열을 한칸 오른쪽으로 옮겨서 다시 처음부터 비교하는 것이 아니라, 그 전에 일치했던 정보(파란색 부분) 를 이용해서 중간 단계를 건너뛰고 4번째 글자부터 비교할 수 있는 것입니다.

A	B	C	D	A	B	C	D	.	.
A	B	C	D	A	B	C	X	.	.
.	.	.	.	A	B	C	D	.	.

 

 

Problems

https://www.acmicpc.net/problem/1786