KMP 알고리즘

 

일반적인 문자열 비교 알고리즘은 시간 복잡도가 $O(NM)$으로 매우 느리다.

$$ O(NM) $$

$$ O(N+M) $$

하지만 KMP 알고리즘을 사용하면 $O(N+M)$에 가능하다.

KMP 알고리즘의 아이디어

문자열 s와 패턴 p가 주어졌을 때 단순 무식한 방법으로는 O(s*p)가 걸린다.

KMP알고리즘은 이 과정에서 낭비되는 정보를 이용하자는 아이디어에서 시작된다.

예를 들어보자

INDEX   : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN : A B C D A B E
                      ^

주어진 문자열과 패턴을 단순 무식한 방법으로 비교할 때 인덱스6에서 일치하지 않아 비교에 실패했다면, p를 한 칸 뒤로 옮겨 비교할 것이다. 하지만, 이미 “알고 있는” 정보를 활용하면 이를 “점프”할 수 있다.

0, 1인덱스의 패턴을 4,5로 바로 옮기면 처음부터 비교하지 않고 그 상태에서 시작할 수 있다.

[단순 무식한 방법]
INDEX   : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :   A B C D A B E
            ^
            
[점프 방법]
INDEX   : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :         A B C D A B E
            

특정 부분이 일치하는지 알려면 prefix와 suffix의 개념이 필요하다.

prefix란 문자열의 인덱스 0부터 시작하는 부분문자열이다.

suffix란 문자열의 마지막 인덱스까지 포함하는 부분문자열이다.

banana의 prefix: b, ba, ban, bana, banan, banana
banana의 suffix: a, na, ana, nana, anana, banana

이제 “점프”를 하기 위해 prefix와 suffix가 일치하는 길이의 배열을 알아야한다. 이를 pi라고 한다.

단, prefix ≠ s_i이다. 즉, pi[i]의 길이는 부분문자열 s_i의 길이보다 작아야한다.

예시로 “ABAABAB”의 pi를 구해보자.

i      부분문자열       값(길이)
0      A             0
1      AB            0
2      ABA           1
3      ABAA          1
4      ABAAB         2
5      ABAABA        3
6      ABAABAB       2

다시 아까의 예제로 돌아가 본다면

인덱스 6에서 실패했으므로 5까지는 일치했다는 의미이다. 따라서 pi[5]를 이용해 PATTERN을 옮기면 된다.

pi[5]의 값은 2이다. 길이 2라는 의미이고, PATTERN index의 2부터 시작하면 된다는 뜻이다.

T_INDEX : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN : A B C D A B E
                      ^
P_INDEX : 0 1 2 3 4 5 6

> p_index == 6에서 실패 p_index = pi[p_index] = 2
> t_index는 유지

T_INDEX : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :         A B C D A B E
                      ^
P_INDEX :         0 1 2 3 4 5 6

> 일치, p_index++, t_index++

T_INDEX : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :         A B C D A B E
                      ^
P_INDEX :         0 1 2 3 4 5 6

> 불일치. pi[2] = 0
> t_index 유지

T_INDEX : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :             A B C D A B E
                      ^
P_INDEX :             0 1 2 3 4 5 6

> (패턴이 이미 인덱스를 벗어났기 떄문에 굳이 비교할 필요는 없지만 알고리즘상 진행)
> 불일치. p_index = 0이기 때문에 pi 이용 불가
> 따라서 t_index++;

T_INDEX : 0 1 2 3 4 5 6 7 8 9 0 1
TEXT    : A B C D A B C E K O I P
PATTERN :               A B C D A B E
                        ^
P_INDEX :               0 1 2 3 4 5 6

> 계속 진행...

구현

pi 구현

pi를 단순 무식하게 구현하면 O(N^3)이다.. 모든 부분수열 N, 단순 무식하게 두 문자열을 비교하는 것을 N^2

하지만 pi 또한 kmp를 구현하는 방법과 유사하게 구할 수 있다.

kmp를 구하는데 pi가 필요하지만, pi를 구하는데에도 pi가 필요하다. 그리고 부분문자열 길이 이전의 pi만 필요하기 때문에 걱정할 필요가 없다.

• i: 기준 문자열의 인덱스
• j: 패턴 문자열의 인덱스

vector<int> getPi(const string& s) {
	int m = s.size();
	vector<int> pi(m, 0);
	int j = 0;
	for(int i = 1; i < m; i++) {
		while(j > 0 && s[i] != s[j]) { // jump
			j = pi[j-1];
		}
		if(s[i] == s[j]) { // find next
			pi[i] = ++j;
		}
	}
	return pi;
}

kmp 구현

vector<int> kmp(const string& s, const string& p) {
	int n = s.size();
	int m = p.size();
	int j = 0;
	vector<int> pi = getPi(p);
	vector<int> ans;
	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); // s기준 시작 index
				j = pi[j]; // 일치하니까 j-1이 아닌 pi[j]를 통해 다음 패턴 탐색
			} else {
				j++;
			}
		}
	}
	return ans;
}

 

참고:

https://bowbowbow.tistory.com/6