KMP 알고리즘(KMP Algorithm)

Knuth-Morris-Pratt Algorithm, KMP Algorithm

 

KMP 알고리즘을 학습하기에 앞서

기존에 흔히 사용하던 C언어의 strstr(), C++ STL의 find(), Java의 indexOf()는 구현하기는 매우 쉽지만, 매우 긴 문자열이 있는 곳에서 이용하기에는 단점이 존재한다.

예를들어 어떤 긴 문자열에서 "abcabcabc"를 찾는다고 가정해보자. 

이때 어떤 긴 문자열이 ~abcabcabd~였다면 위의 3가지 함수는 다음과 같이 해석하게 된다.

'아, 마지막이 c가 아니고 d이니 아니구나.. 다음 문자열부터 찾아봐야지'라고 생각하고 

이번엔~abcabcabd~의  짙은 부분인 b부터 찾기 시작한다.

이 과정은 이미 abcabcab까지는 맞았지만 c와 d가 다르다는것이기에 굳이 b부터 다시 찾아볼 필요가 없다는 것을 착안하여 만들어 진 알고리즘이다.

또 다른 예시를 들어보자

문자열 aaabbbdbcaaabbbaaa가 있는데 찾고자 하는 문자열이 "aaabbbaaa"였다고 생각해보자.

이때 aaabbbdbc의 d에서 불일치가 발생하고 그다음 aaabbbaaa에서 일치가 발생하기에 결국 검색에 성공하였다.

이 과정에서 느낄 수 있는 점은 이미 b에서 불일치가 발생하였기에 그 전 내용은 모두 생략할 수 있고, 찾고자 하는 문자열을 처음과 같은 문자열이 있는 곳에서 다시 시작하면 찾을 수 있다는 것이다. 

즉, 시작 위치를 움직인 이후 첫 글자부터 다시 대응시켜 나갈 필요가 없다는 것이다.

이러한 KMP 알고리즘을 이용하기 위해서는 실패 함수라는 테이블을 미리 생성해 두어야 한다.

이 실패 함수는 찾고자 하는 패턴에 대해 생성하는 테이블이다.

실패 함수를 구하기 위한 테이블

 

arr = "aabaabac"패턴에 대한 테이블을 보자.

가정.

N[i] :: arr[0~i]까지의 문자열

　　　이때, 하늘색 = 접미사와 일치하는 접두사, 분홍색 = 접두사와 일치하는 접미사, 보라색은 겹쳐져서 색이 짙어진 색이다.

str :: 접두사이면서 접미사인 최대 문자열

f[i] :: str의 크기(실패 함수라고 부른다.)

i	0	1	2	3	4	5	6	7
N[i]	a	aa	aab	aaba	aabaa	aabaab	aabaaba	aabaabac
str	-	a	-	a	aa	aab	aaba	-
f[i]	0	1	0	1	2	3	4	0

KMP 알고리즘의 시간 복잡도

패턴 arr에서 실패함수(f[i])를 구하는 부분과 이를 이용하여 전체 문자열에서 arr를 찾는 부분으로 나누어 생각할 수 있다.

실패함수를 찾는데 걸리는 시간 O(m), 전체 문자열에서 패턴 arr을 찾는 시간 O(n)이므로 총 O(n+m)의 시간이 소모된다.

KMP 알고리즘의 이용 예시

위의 표를 이용하여 KMP 알고리즘을 어떻게 쓸 수 있는지 알아보자.

이 내용을 집중하여 잘 본다면 KMP 알고리즘에 대해 잘 이해 할 수 있을 것이다.

aabaabaaaabaabaadaabaabac가 있다고 가정하자.

여기서 aabaabac를 찾으려 한다면 위의 표를 다음과 같이 이용하면 된다.

aabaabaaaabaabaadaabaabac

aabaabac

비교결과 :: aabaaba까지 같다. 따라서 arr[i]의 7번째 인덱스에서 a와 c가 틀렸으니,

aabaaba의 f[i] = 4 따라서 (7-4) = 3인 arr[3]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　  aabaabac

비교결과 :: aabaa까지 같다. 따라서 arr[i]의 8번째 인덱스에서 a와 b가 틀렸으니,

aabaa의 f[i] = 2 따라서 (8-2) = 6인 arr[6]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　 aabaabac

비교결과 :: aa까지 같다. 따라서 arr[i]의 8번째 인덱스에서 a와 b가 틀렸으니,

aa의 f[i] = 1 따라서 (8-1) = 7인 arr[7]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　aabaabac

비교결과 :: aa까지 같다. 따라서 arr[i]의 9번째 인덱스에서 a와 b가 틀렸으니,

aa의 f[i] = 1 따라서 (9-1) = 8인 arr[8]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　  aabaabac

비교결과 :: aabaaba까지 같다. 따라서 arr[i]의 15번째 인덱스에서 a와 c가 틀렸으니,

aabaaba의 f[i] = 4 따라서 (15-4) = 11인 arr[11]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　　　aabaabac

비교결과 :: aabaa까지 같다. 따라서 arr[i]의 16번째 인덱스에서 d와 b가 틀렸으니,

aabaa의 f[i] = 2 따라서 (16-2) = 14인 arr[14]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　　　　  aabaabac

비교결과 :: aa까지 같다. 따라서 arr[i]의 16번째 인덱스에서 d와 b가 틀렸으니,

aa의 f[i] = 1 따라서 (16-1) = 15인 arr[15]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　　　　　aabaabac

비교결과 :: a까지 같다. 따라서 arr[i]의 16번째 인덱스에서 d와 a가 틀렸으니,

a의 f[i] = 0  따라서 (16-0) = 16인 arr[16]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　　　　　  aabaabac

비교결과 :: 같은 것이 없다. 따라서 arr[17]부터 다시 확인한다.

aabaabaaaabaabaadaabaabac

　　　　　　　  aabaabac

비교결과 :: 모두 일치. 정답을 도출한다.( 일치하는 문자열의 시작 인덱스 :: 17, 일차하는 문자열의 개수 :: 1)

아래는 KMP 알고리즘에 대한 소스 코드이며, 여러 문제는 다음 링크를 통해 확인이 가능하다.

http://www.crocus.co.kr/search/kmp

 
vector<int> getPi(string p) 
{
    int m = (int)p.size();
    int j = 0;
 
    vector<int> pi(m, 0);
 
    for (int i = 1; i< m; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];
        if (p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
 
vector<int> kmp(string s, string p) 
{
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j>0 && s[i] != p[j])
            j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j == m - 1) {
                ans.push_back(i - m + 1);
                j = pi[j];
            }
            else {
                j++;
            }
        }
    }
    return ans;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>