KMP 알고리즘 완전히 파헤치기 - 문자열 검색

 

드디어 알고리즘 첫 번째 포스팅입니다. (미라클 모닝은 물건너 간 것인가.. 새벽에--b 역시 올빼미에서 벗어날 수 없는 걸까요..)

 

"tomatitomatomato"라는 문자열이 있습니다.  멋쟁이 "tomato"를 찾고 싶은데 몇 개나 있을까요?

문자열에서 "tomato" 는 앞뒤로 겹쳐 보일 수도 있습니다.

※ 예로  "ababa" 에서 "aba" 는 2개로 취급합니다. 

 

1. naive 한 접근

우직하게 처음부터 한글자씩 비교하여 찾아봅니다.

총 16 길이의 text 문자열에서 길이6의 "tomato"를 11번(16 - 6 + 1) step 만큼 찾아봐야 합니다.

또한 각 step 별로 6글자인 "tomato" 를 6번씩 비교하게 됩니다.총 66번

 

step 7, step 11번 index에 "tomato" 가 있네요.

고생끝에 2개의 "tomato"를 찾았습니다^^b

 

정리하면 naive한 접근을 하면 text 길이를 N, pattern 길이를 M으로 했을 때 O(NM) 만큼 시간이 걸립니다.

 

 

 

 

 

 

---

2. KMP 알고리즘 이용

KMP 알고리즘이란 Knuth, Morris, Prett라는 사람들이 만들었다고 해서 앞글자를 딴 KMP 알고리즘입니다.

 

이 방법 역시 왼쪽에서 오른쪽 순으로 비교를 하게되지만, naive한 방법과는 다르게 KMP 알고리즘은 찾고자 하는 문자열의 접두사(prefix)와 접미사(suffix)를 이용하여 체크할 필요없는 문자열은 길게 건너 뛸수 있게 합니다.

 

우선 prefix-suffix 일치 개수 테이블을 만듭니다.

 

 

 

 

왼쪽부터 오른쪽으로 한글자씩 비교를 해봅니다.

step 1에서 6번째 문자열인 i에서 틀렸음을 알 수 있습니다.

 

 

 

 

비록 6번째 문자열이 불일치하였지만 슬퍼할 필요가 없습니다.

이미 이전 문자열 1 ~ 5번까지는 일치하고 있고 부분 문자열의 prefix인 "t"와 suffix인 "t"가 1개 일치함을 알 수 있습니다.

 

 

 

 

부문 문자열이 1개 일치한 정보를 이용하여, pattern의 첫 번째 문자열인 t에서 +1을 한 o 문자열을 기준으로 step 1에서 틀렸던 6번째 index로 전체 pattern 문자열을 step 2에서 이동합니다.

이 말은 step1에서 suffix와 "t"와 일치한 prefix "t"를 step 2에서 index 5로 이동시키고 index 6번 부터 다시 비교를 시작하는 것과 같습니다.

 

 

 

 

다시 6번 index에서 문자를 비교해보니 또 틀렸네요. 

 

 

 

 

이제는 6번 index 문자열에서 더이상 비교가 불가능하므로

step3에서 text 문자열에서 비교할 index를 7번으로 옮기고 pattern 문자열은 첫번째 문자열부터 비교를 시작합니다. 

 

모든 문자열이 일치하네요. 금방 "tomato"를 찾았습니다^^b naive한 방법에서는 step 7에서 찾은 반면 4 step을 단축 시켰습니다.

 

 

 

다음 비교를 위해 pattern 문자열을 살펴보겠습니다.

prefix-suffix가 같은 부문 문자열 개수가 "to"-"to"로 2개이네요.

 

 

 

 

step 4에서 부문 문자열 개수 정보인 2를 이용하여, pattern의 첫 번째 문자열인 t에서 +2을 한 m 문자열을 기준으로 13번째 index로 전체 pattern 문자열을 이동합니다.

 

 

 

"tomato"를 찾았습니다. step 4번만에 찾았네요. 수고하셨습니다^^b

 

 

KMP 알고리즘은 보다시피 text의 N 길이만큼 쭈욱 나가면서 pattern의 문자열을 바로 비교 해버리고, text의 문자열에서 한번 비교했던 문자는 그 다음 step에서 다시 비교하지 않으므로 최악의 경우 O(N) 시간이 걸리게 됩니다.

 

---

다음은 c언어로 구현한 코드입니다.

 

https://github.com/aiemag/algorithm/blob/master/string/kmp.cpp

#include <stdio.h>
#define MAX_N 100000
 
int skip[MAX_N];
 
int mstrlen(char* str) {
    int n = -1;
    while (str[++n]);
 
    return n;
}
 
void make_skip_table(char* str, int len) {
 
    for (int i = 0; i < MAX_N; i++) {
        skip[i] = 0;
    }
 
    int j = 0;
    for (int i = 1; i < len; i++) {
        while (j > 0 && str[i] != str[j])
            j = skip[j - 1];
 
        if (str[i] == str[j])
            skip[i] = ++j;
    }
}
 
int do_kmp(int N, char *text, int M, char *pattern) {
    make_skip_table(pattern, M);
 
    int cnt = 0, j = 0;
 
    for (int i = 0; i < N; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = skip[j - 1];
        }
 
        if (text[i] == pattern[j]) {
            if (j == M - 1) {
                printf("found : %d\n", i+1);
                cnt++;
                j = skip[j];
            }
            else {
                j++;
            }
        }
    }
 
    return cnt;
}
 
int main() {
 
    char a[] = "tomatitomatotomato";
    char b[] = "tomato";
 
    int found = do_kmp(mstrlen(a), a, mstrlen(b), b);
    printf("found count : %d\n", found);
 
    return 0;
}

 

제 설명에 잘못된 내용이 있거나 오류 있으면 알려주세요!

 

다음 시간에는 다른 방법으로 문자열 검색을 해보겠습니다. (to be continued)