KMP 알고리즘(Knuth-Morris-Pratt Algorithm)

KMP 알고리즘은 문자열 S에서 패턴 P를 선형 시간에 찾는 알고리즘이다.

 

S와 P의 길이를 각각 n, m이라고 하자.

가장 간단하게 S의 모든 지점에서 시작해보면서 P와 비교하는 방법은 O(NM)의 시간복잡도를 가진다.

이 때 어디에서 시작해서 어디까지 일치했는지에 대한 정보를 토대로 다음에 시작할 위치를 효과적으로 소거할 수 있으며, 이것이 KMP 알고리즘의 핵심 아이디어이다.

 

1. KMP 알고리즘

위 그림은 P의 처음 다섯 문자가 일치했으며, 여섯 번째 문자에서 불일치가 발생한 경우를 나타내고 있다. O(NM)의 방법에서는 이 경우 P를 오른쪽으로 한 칸 움직인 후 첫 문자부터 다시 비교를 시작한다. 하지만 일치했던 문자열 "abcab"의 접두사이면서 접미사인 최대 길이 문자열이 "ab"라는 점을 이용하면 "ab"만 일치하도록 P를 오른쪽으로 세 칸 움직인 후 불일치가 발생했던 위치에서 다시 비교를 시작해도 된다.

여전히 해당 위치가 불일치라면, 위 작업을 반복해서 수행하면 된다. 이런 식으로 진행하면, 매 순간 P가 오른쪽으로 적어도 한 칸 움직이거나, 비교하는 위치가 오른쪽으로 한 칸 움직이는 두 가지 중 하나가 수행되므로, 패턴을 찾는 과정이 O(N+M)에 동작하게 된다.

 

2. 실패 함수(failure function)

위 방법을 사용하려면, 패턴 P의 각 prefix에 대해 그것의 접두사이면서 접미사인 최대 길이 문자열(단, 자기 자신 제외)의 길이를 미리 계산해둬야 한다. 이 값을 패턴 P의 실패 함수(failure function)라고 부른다.

패턴 P="abaabab"인 경우 다음과 같이 계산된다.

 

i	P[0..i]	실패함수 f(i)
0	a	0
1	ab	0
2	aba	1
3	abaa	1
4	abaab	2
5	abaaba	3
6	abaabab	2

 

잘 생각해보면 이것은 문자열 P[1..]에서 패턴 P를 찾는 KMP 알고리즘으로 O(M)에 똑같이 계산할 수 있다.

f(i): 문자열 P[1..]에서 패턴 P를 찾는 KMP 알고리즘을 수행하는 과정에서 i번 위치를 비교하고 있을 때의 일치하는 최대 길이

i번 위치를 비교하고 있을 때의 일치하는 최대 길이는 P[0..i]의 자기 자신을 제외한 suffix와 prefix가 일치하는 최대 길이를 의미하기 때문이다.

 

f(5)와 f(6)을 구하는 시점에서의 KMP 알고리즘의 수행과정은 다음과 같다.

5번 위치를 비교하고 있는 상황. 3개의 문자가 일치하므로 f(5) = 3이다.

6번 위치에서 불일치가 일어났다.

불일치가 일어난 경우 "aba"의 접두사이면서 접미사인 최대 길이 문자열의 길이를 찾아야 하는데, 이는 P[0..2]의 실패함수 값인 f(2)이므로 1로 이미 계산되어 있다. 따라서 "a" 한 문자만 일치하도록 P를 오른쪽으로 두 칸 밀고 다시 비교하면 다음과 같다.

6번 위치에서 2개의 문자가 일치하므로 f(6) = 2이다.

코드

void kmp(){
    for(int i = 0, j = 0; i < m; i++){
        while(j && S[i] != P[j]) j = f[j - 1];
        if(S[i] == P[j]) j++;
        if(j == n){
            // matched: S[i-n+1..i] = P
            j = f[j - 1];
        }
    }
}

void calc_fail(){
    f[0] = 0;
    for(int i = 1, j = 0; i < n; i++){
        while(j && P[i] != P[j]) j = f[j - 1];
        if(P[i] == P[j]) j++;
        f[i] = j;
    }
}