[알고리즘 소개] String Algorithm - KMP algorithm

문자열 알고리즘의 대표적인 알고리즘 되시겠다. Knuth–Morris–Pratt 세 명의 첫 글자를 따서 KMP라고 불린다.

 

어디에 쓰는 알고리즘인고?

우리가 네이버나 구글에 검색어를 치면 검색어가 포함된 게시글을 바로바로 보여준다. 세세한 것은 다르겠다만, “banana”라는 글자를 치면 바로 “banana” 키워드가 있는 게시물을 보여준다.

 

구글에 banana를 검색한 모습

게시물 하나하나에 banana가 들어가있는지 검색해줄 뿐만 아니라 banana 단어에 bold로 표시하면서 게시물에 banana가 있음을 우리에게 확인시켜주고 있다. 이를 빨리 해결하는 데 쓰는 알고리즘이 바로 KMP algorithm 되시겠다.

 

Brute Force 알고리즘 – O(NM)

S1 = “I love apple and banana”

S2 = “banana”

라고 했을 때, 다음과 같이 2중 for문을 써서 해결이 가능하다.

char S1[]="I love apple and banana", S2[]="banana"; int i, j, len1=strlen(S1), len2=strlen(S2); for (i=0;i<len1-len2+1;i++){     for (j=0; j<len2; j++){         if (S1[i+j]!=S2[j]) break;     }     if (j==len2) chk++; }

일반적인 데이터의 경우 나쁘지 않을수도 있지만, 다음과 같은 데이터의 경우 최대 O(NM)이 된다.

(단, N = length(S1), M = length(S2))

S1 = “bbbbbbbbbbbbbbbb”

S2 = “bbbbbbbba”

 

Brute Force 알고리즘의 문제점 : 너무 중복되는 비교횟수

빨강색으로 칠한 b는 뭔가 줄일 수 있어 보인다.

여기도 마찬가지

위의 예시에서 빨강색으로 표시한 부분은 분명히 불필요하게 중복이 되는 것처럼 보인다. 이것을 “잘” 처리하면 중복처리 없이 잘 해결할 수 있을 것 같다

 

실패함수의 등장

S에 대한 실패함수, fail(i)의 정의는 다음과 같다:

 

0<k<len(S2)를 만족하는 정수 k에 대해서 k보다 작은 정수 l에 대해서

S[0..l-1] == S[k-l...k-1]를 만족하는 최대의 l이 있을 때, fail(k)=l이다.

 

쉽게 말해서 suffix와 prefix가 같을 때 최대길이라고 보면 된다.

수학적으로 설명해서 굉장히 어렵게 느껴지는데, 풀어쓰자면 다음과 같다.

fail(5)=3이다.	fail(6) = 5

 

실패함수를 알게 되면 아래의 예제에서 구태여 i=0에서 i=2로 넘어갈 때 빨강색으로 칠한 부분을 다시 탐색할 필요가 없다! ababab에서의 실패함수는 4이며, 따라서 i=0에서 불일치가 발생하였을 때 바로 시작점을 S1[2]=S1[6-4]로 옮기면 된다!

여기도 마찬가지

 

이를 이용하여 실패함수를 구해놓았다고 가정하였을 때 Brute Force 알고리즘을 개선해보자.

char S1[MAX_N]="abacababaca", S2[MAX_N]="ababa"; int len1 = strlen(S1), len2 = strlen(S2); int i, j = 0, fail[MAX_N]={0}; // fail함수를 구하는 과정은 후술 for (i = 0; i < len1; i++) {     while (j > 0 && S2[j] != S1[i])         j = fail[j-1];     if (S2[j] == S1[i]) {         j++;         if (j == len2) {             cout << "S2 matches at S1[" << i-j+1 << ".." << i << "]" << endl;             j = fail[j];         }     } }

 

시간복잡도는 O(N)이다.

 

실패함수를 어떻게 구하지?

실패함수가 어떤 것이고, 구해놓는다면 어떻게 될 지는 알았다. 이제 한 관문만 남았다. 실패함수를 어떻게 구할까?

실패함수를 구하는 방법은 생각보다 간단하다. S1를 S2로 바꾸고 위 알고리즘을 거의 똑같이 따라하면 된다. 다만, 하나 다른 점이 있다면 위 코드에서 i=1부터 시작하여야 한다.

for (i = 1; i < len2; i++) {     while (j > 0 && S2[j] != S2[i])         j = fail[j-1];     if (S2[j] == S2[i]) {         fail[i] = ++j;     } }

시간복잡도는 O(M)이다.

 

그래서, KMP 알고리즘 구현 - O(N+M)

char S1[MAX_N]="abacababaca", S2[MAX_N]="ababa"; int len1 = strlen(S1), len2 = strlen(S2); int i, j = 0, fail[MAX_N]={0}; for (i = 1; i < len2; i++) {     while (j > 0 && S2[j] != S2[i])         j = fail[j-1];     if (S2[j] == S1[i]) {         fail[i] = fail[j] + 1;     } } for (i = 0; i < len1; i++) {     while (j > 0 && S2[j] != S1[i])         j = fail[j-1];     if (S2[j] == S1[i]) {         j++;         if (j == len2) {             cout << "S2 matches at S1[" << i-j+1 << ".." << i << "]" << endl;             j = fail[j];         }     } }

완성된 소스코드는 위와 같다.

시간복잡도는 실패함수를 구하는 부분(O(M)), 실패함수를 이용하여 S1와 S2가 겹치는 부분을 구하는 부분(O(N))을 더해 O(N+M)이 된다.

 

kmp는 시험에 굉장히 많이 나오는 편이고, 굉장히 강력한 알고리즘이다. 조금이라도 알고리즘 대회에 관심이 있다면 이 알고리즘은 필수적으로 알아놓는 것이 좋을 것이다.