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

문자열 S와 T가 주어졌을 때, S의 부분 문자열 중 T가 몇번 등장하는 지를 찾는 문제를 생각해보자. 예를 들어 "koosaga" 에서 "saga" 를 찾으면

"koos" != "saga", "oosa" != "saga", "osag" != "saga", "saga" == "saga"

여서 총 한번 등장하고, "aa" 를 찾으면

"ko" != "aa", "oo" != "aa", "os" != "aa", "sa" != "aa", "ag" != "aa", "ga" != "aa"

여서 단 한번도 등장하지 않는다.

N = (S의 길이), M = (T의 길이) 라 하자. S[i, j] = (i번째 문자에서 j-1번째 문자까지를 포함하는 부분 문자열) 이라고 하자. 예를 들어 "koosaga"[0, 3] = "koo" 이다. 0번째를 기준으로 서술한다.

1. 간단한 O(NM) 알고리즘

S의 부분 문자열 (substring)의 시작 위치를 지정한다. 그 후, 해당 위치에서 시작하는 부분 문자열과, T가 똑같은 지 판별한다. 위에서 했던 방법이랑 완전히 똑같은 방법이라고 할 수 있다. 

일반적으로 구현 시에는 이보다 더 최적화된 방법을 쓴다. 대표적으로, 다른 위치가 나오는 즉시 판별을 멈추고 다음 위치를 시작하는 식의 커팅이 널리 쓰인다. (이는 Knuth Morris Pratt 알고리즘 구현에서도 기초가 된다) 이것만으로도 일반적인 상황에서는 나쁘지 않다고 알려져 있다. 그럼에도 NM을 결코 피할 수 없는 데이터들을 충분히 만들 수 있기 때문에 ("aaaa......aaabaaaaa......aaabaaaa...", 그리고 충분히 긴 "aaaa" 문자열) 좋은 알고리즘이라고 하기는 쉽지 않다. 

2. Knuth-Morris-Pratt 알고리즘 : Failure function 아이디어, 그리고 O(M^3 + N) 구현

Knuth-Morris-Pratt 알고리즘은 간단하지만 독특한 아이디어로 이 알고리즘을 최적화한다. 관찰해야 할 것은, 문자열의 매칭을 상당히 진행시키고 나서, 나중에 이것이 성공 / 실패로 확인이 되면 다음 부분문자열로 돌아가야 한다는데, 이 부분이 낭비가 너무 심하다는 것이다. 조금 줄일 수 있을까.

예를 들어, 현재 abcdebcdf에서 bcdf를 찾는다고 하자. 이 경우 일어나는 일을 그려보면

 * a..는 b.. 와 다르므로 스킵이 된다.

 * bcde는 bcdf와 다르므로 모두 확인하고 넘어간다

 * c.. 는 b.. 와 다르므로 넘어간다

 * d.. 는 b.. 와 다르므로 넘어간다

 * e.. 는 f.. 와 다르므로 넘어간다.

2번째 스텝에서 많은 계산량이 필요했음을 알 수 있다. 만약에 이 계산량만큼의 이득을 어떻게든 취할 수 있다면 (예를 들어, 계산량 만큼 뒤의 계산을 스킵할 수 있다거나) 좋을 것이다. 여기서

 * M이 작으니 M에 대해서 엄청나게 계산량이 큰 전처리를 해도 상관이 없다.

 * 굳이 복잡도 보장이 안 돼도 그럴듯한 커팅이면 한다.

이런 걸 상정하고 생각해보자.

bcde와 bcdf가 다르다는 사실이, c... / d... / e... 의 mismatch를 알려줄 수 있을까? 저 위치가 볼 가치가 있을 가능성을 잘 정리해 보자. 우리는 현재 bcd까지는 string에서 매칭이 됐다는 사실을 확인을 했다. 그렇다면

 *  "cd" == "bc" 일 경우, 혹은 T[1, 3] == T[0, 2]일 경우, 볼 가치가 있다

 * "d" = "b" 일 경우, 혹은 T[2, 3] == T[0, 1]일 경우, 볼 가치가 있다

이 사실을 일반화하자, 현재 T에서 k개의 문자까지가 매칭이 되었는데, k번째 문자가 매칭에서 벗어난다. 이 때 T[0, i] = T[k-i, k] 일 경우, k - i - 1번 뒤로 넘어갈 수 있다. 그러면, 저것을 만족하지 않는 위치들은 절대 볼 필요가 없다는 것을 쉽게 알 수 있다. 

이제, 우리가 넘어가야 할 것은, 저것을 만족하는, 여기서 가장 가까운 위치이다. 즉, T[0, i] = T[k-i, k] 을 만족하는 가장 큰 i를 찾고, 이 위치로 넘어가면 된다. 그러면 T의 각 문자열에 대해서 Fail[k] 를 정의하자 : 

 * Fail[k] = (T[0, i] = T[k-i, k]) 를 만족하는 가장 큰 i < k (i == k인 경우는 당연히 제외해야 한다. 다음 이동에 도움이 안 되는 정보이니)

다시 말해서, T의 앞 k개 문자로 이루어진 prefix중, prefix와 suffix가 똑같은 가장 긴 문자열의 길이를 계산하는 것이다. 정의 그대로 M^3에 계산할 수 있다.

이제, 이 테이블을 통해서 최적화된 문자열 매칭을 해 보자. i는 현재까지 본 문자열의 길이, p는 현재 매칭된 최대 문자열 길이라고 하면, (끝점을 움직인다)

for(int i=0; i<N; i++){

if(S[i] != T[p]){

???

}

if(S[i] == T[p]) p++;

if(p == M) match++;

}

와 같은 코드가 나올 것이다. 이 알고리즘은 [i - p, i] 까지 매칭이 기존에 되어 있을 때, 이를 [?, i+1] 로 바꿨을 때 얼마나 매칭이 유지될 수 있는지를 확인한다. (끝점 기준으로 iteration을 돌린다.) 상황은 i - p에서 i + 1까지는 매칭이 안 된다는 것인데, 그렇다면 i - p에서 점프할 수 있는 가장 가까운 위치는 i - fail[p]이다. (그 사이 위치는 앞 정의에 따라서 가능치 않다.) 그렇다면 매칭을 찾을 때까지 이렇게 점프를 해야 할 것이다. 이는

for(int i=0; i<N; i++){

while(p > 0 && S[i] != T[p]) p = fail[p];

if(S[i] == T[p]) p++;

if(p == M) match++;

}

이렇게 아주 간단한 코드로 나온다. 

while문이 있는데 시간 복잡도는 어떻게 될까? fail[p] < p이므로 각각의 while iteration에서 p는 최소 1씩 줄어든다. 한편, p를 증가시킨 횟수는 많아야 N이다. 고로, p의 증가 + 감소 횟수가 O(N) 이고, 시간 복잡도는 O(N + M^3) 이라고 할 수 있다.

3. Knuth-Morris-Pratt 알고리즘 : Failure function의 최적화와 O(M + N) 구현

Failure function을 계산하는 것을 최적화할 수 있을까? 생각보다 아주 간단하다. 문자열 T[1, M]에서, 문자열 T[0, M]을 찾는 KMP를 돌린다고 생각해보자. T[0, M]에 대한 Failure function이 있다면, prefix를 돌면서 T[0, M]에서 얼마나 매칭되었는 지를 가져갈 때, 이 매칭량이 항상 최대를 유지하므로, 매칭 량만 가지고 Failure function을 만들 수 있다. 즉, 

for(int i=1; i<M; i++){

while(p > 0 && T[i] != T[p]) p = fail[p];

if(T[i] == T[p]) p++;

fail[i + 1] = p;

}

이 말만 들으면, Failure function이 있을 때 Failure function을 만드는 게 무슨 의미냐고 할 수 있겠지만, 생각해보면 항상 p < i를 유지하며, fail[1]은 당연히 0이다. 즉 이 과정 자체가 DP처럼 재귀적인 식을 만들어 내는 것이다! fail[2]를 알기 위해서 알아야 할 것은 fail[1]밖에 없고, fail[3]을 알기 위해서 알아야 할 것은 fail[1], fail[2]... 코드를 보면 이를 이해할 수 있을 것이다. 고로 시간 복잡도 O(M)에 failure function을 구할 수 있다. 

4. Failure function과 유한 상태 오토마타

KMP의 failure function은 일종의 유한 상태 오토마타로 해석할 수 있다. 만약 스트링 S가 주어졌을 때, 이 스트링과 T가 매칭이 되는 지를 확인하려면 

* 0번 노드에서 시작한다 

* 각각의 문자를 순서대로 넣고, 오토마타에 정의된 상태를 따라간다 

* M번 노드에 도달하는 지 확인한다

와 같은 procedure를 거친다. 이를 사용해서 KMP에 DP를 결합하는 등의 응용이 가능하다. DP의 상태로 현재 매칭된 스트링의 길이를 넣고, 다음 원소를 시도해 보면서 state를 전이시키는 식의 방법이다. 연습 문제

도움이 될 수 있는 다른 글도 소개한다 : http://blog.myungwoo.kr/101