1. 개요

- Knuth - Morris - Pratt 알고리즘의 약자로, 찾고자 하는 단어를 긴 문자열 내에서 검색하는 문자열 검색 알고리즘의 하나다. 알고리즘의 발견자들인 James Morris, Donald Knuth, Vaughan Pratt의 이름을 따서 지어진 이름이다.

- 이와 같은 문자열 검색 알고리즘을 완전탐색_(긴 문자열 인덱스 하나하나를 시작점으로 해서, 그 지점에서부터 검색 단어가 문자열과 일치하는지 확인)_으로 구현할 경우 시간복잡도가 O(nm)이 되나, KMP 알고리즘을 사용하면 O(n+m) 내에 구현 가능하다.

2. 기본 개념

- KMP 알고리즘은 기본적으로 완전탐색 알고리즘 수행 시와 마찬가지로 긴 문자열(S)의 i번째 인덱스에서 시작해 단어 일치 여부를 확인하되, 일치하지 않음이 확인됐을 때는 완전탐색 알고리즘에서처럼 i+1번째 인덱스와 검색단어(W)의 0번 인덱스에서부터 다시 단어 일치 여부를 검사하는 게 아니고, i+\(\pi(x)\)번째 인덱스와 W의 \(\pi(x)\)번째 인덱스(0<\(\pi(x)\)<W의 길이)에서 다시 단어 일치 여부를 검사해 검색 시간을 단축시킨다.

- 구체적으로, KMP 알고리즘에서는 W의 각 부분문자열이 접두사와 접미사가 일치하는 길이를 미리 구해 배열에 저장해둔다. (이 배열의 경우 \(\pi (x) \) : 0번 인덱스부터 \(x\)번 인덱스까지의 부분문자열의 접두사와 접미사가 일치하는 길이 로 정의되며, 흔히 ‘실패함수(failure function)’이라 부른다.) 이 값을 미리 저장해둔 후, S[i]와 W[j]가 일치하지 않을 때 \(\pi(x)\) 값을 이용해 다시 일치여부를 확인하기 시작할 위치를 선형시간보다 빠른 시간 내에 찾아내는 것이 KMP 알고리즘의 핵심 개념이다.

* KMP 알고리즘이 시간이 단축되는 구체적인 이유

- 완전탐색 알고리즘의 경우 S[i+j] != W[j]라면 그 다음으로 S[i+1]과 W[0]의 일치여부를 확인해야 한다. 그러나 KMP 알고리즘에서는 W[0] … W[j]라는 W의 부분문자열의 접두사와 접미사가 일치하는 길이를 미리 저장해두기 때문에, S[i+j] != W[j] 임을 확인하게 되었더라도, W[0]으로까지 다시 돌아가지 않고 W[0] … W[j]의 접두사까지로만 돌아가 거기서부터 다시 일치여부를 확인할 수 있다. 이렇게 하면 불일치가 나타날 때마다 완전탐색에 비해 그 접두사 길이만큼 일치여부 확인 횟수를 절약할 수 있다.

3. 예시

W = “abbababba”이라 할 경우, \( \pi(x) \) 는 다음과 같이 구해진다.

  0 1 2 3 4 5 6 7 8
$ \pi(x) $ 0 0 0 1 2 1 2 3 4

S = “abbababbc”이라 할 경우, S[8] != W[8]이다. 이 경우 \(\pi(7)\) = 3 이므로, W[0]…W[7]의 접두사인 W[0]…W[2]이 S[5]…S[7]와 일치한다는 정보를 활용해 W[3]까지만 돌아가 다시 일치여부를 확인한다.

한편, 이 사례와 같이 W[3]으로 돌아갔는데도 S[8]이 이와 일치하지 않는 경우, W[0]…W[2]의 접두사를 다시 찾아가는 루프를 수행해 다시 일치여부를 확인한다.

4. 구현

1) 실패함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

vector<int> failure_function(string W)
{
    vector<int> pi(W.length());
    
    pi[0] = 0;
    for (int i=1, j=0; i < W.length(); i++)
    {
        while(W[i] != W[j])
            if (j >= 1) j = pi[j-1];
            else break;
        //실패함수의 각 값이 W[0]...W[j] 부분문자열의 접두사-접미사의 일치 길이를 담고 있으므로,
        //이 특성을 이용한 루프를 통해 실패함수의 값을 채울 수 있다.
            
        pi[i] = (W[i] == W[j]) ? ++j : 0;
    }
    
    return pi;
}

2) KMP 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int KMP(string S, string W)
{
    vector<int> pi = failure_function(W);
    
    for (int i=0, j=0; i < S.length(); i++)
    {
        while(S[i] != W[j])
            if (j >= 1) j = pi[j-1];
            else break;
        //KMP 알고리즘의 핵심인 루프. 이 루프를 이용해, S[i] != W[j]인 상황에서
        //W에서 다시 S와 비교해야 할 위치를 빠른 시간 내에 찾아낼 수 있다.
            
        if (S[i] == W[j])
        {
            j++;
            if (j == W.length())
                return i - W.length() + 1;
        }
    }
    
    return -1;
}