[알고리즘] KMP 알고리즘 (Knuth-Morris-Pratt)

KMP 알고리즘 (Knuth-Morris-Pratt)

 

일반적으로 어떤 문서나 파일에서 특정 문자열을 찾기 위해 Ctrl + F를 활용해 찾기를 시도합니다. 이러한 행위가 바로 문자열 탐색, 혹은 문자열 검색입니다. 

 

문자열 검색은 다음과 같은 알고리즘에 의해 수행됩니다.

A	B	C	D	E
C	D
결과 : 실패

검색을 당하는 문자열은 ABCDE 이며 검색하려는 문자열은 CD 입니다. ABCDE의 앞자리부터 검색할 문자열 CD를 하나씩 대조하며 탐색을 시작합니다. 일치하지 않으므로 한칸 이동합니다

A	B	C	D	E
	C	D
결과 : 실패

역시 일치하지 않으므로 한칸 이동합니다.

A	B	C	D	E
		C	D
결과 : 일치

문자열이 일치하여 검색에 성공합니다. 만약 검색 당한 문자열이 ABCDEABCDE 처럼 길다면 CD 문자열은 총 2번 검색됨을 알 수 있습니다. 

하지만 이 알고리즘은 구현이 쉽고 단순하지만 시간 복잡도는 O(NM)이므로 비교적 비효율적인 알고리즘입니다. 이러한 알고리즘을 더 빠르게 수행하기 위해 고안된 알고리즘이 KMP 알고리즘입니다.

 

KMP알고리즘을 구현하기 위해 알아야 할 것은 첫째, 접두사(Prefix)와 접미사(Suffix)입니다. 

문자열 'yjglab'을 예로 들자면,

접두사는 y, yj, yjg, yjgl, yjgla, yjglab이며 접미사는 b, ab, lab, glab, jglab, yjglab 입니다.

한마디로 문자열의 앞에 있는 부분과 뒤에 있는 부분입니다.

 

둘째, 접두사와 접미사가 일치하는 문자의 최대 길이를 구해야 합니다.

다음 예시를 보겠습니다.

INDEX	STRING	MAX LENGTH
1	A	0
2	AB	0
3	ABA	1
4	ABAD	0
5	ABADC	0
6	ABADCA	1
7	ABADCAB	2
8	ABADCABA	3

위와 같이 ABADCA의 접두와와 접미사가 A로 하나 일치하므로 최대 일치길이가 1이되고, ABADCABA의 접두사와 접미사가 ABA로 세개 일치하므로 최대 일치길이를 3으로 볼 수 있습니다.

 

알고리즘 원리 - 최대 일치 길이 구하기

최대 일치 길이를 구하는 알고리즘 예시는 다음과 같습니다. 접두사와 접미사를 하나씩 늘려가며 비교하면서 일치하지 않으면 일치했던 부분으로 돌아가서 다시 검색을 시작하게 됩니다.

	A	B	A	D	C	A	B	A
i		●
j	●
MAX	0	0	0	0	0	0	0	0

i는 1번 index부터 비교합니다. i가 B, j가 A로, 일치하지 않으므로 i를 1증가시킵니다.

	A	B	A	D	C	A	B	A
i			●
j	●
MAX	0	0	1	0	0	0	0	0

i와 j가 서로 일치하므로 i와 j를 모두 1증가시킵니다.

	A	B	A	D	C	A	B	A
i				●
j		●
MAX	0	0	1	0	0	0	0	0

i와 j가 일치하지 않으므로 마지막으로 일치했던 값으로 돌아가기 위해 j를 1감소시킵니다.

	A	B	A	D	C	A	B	A
i					●
j	●
MAX	0	0	1	0	0	0	0	0

i와 j가 일치하지 않으므로 i를 1증가시킵니다.

	A	B	A	D	C	A	B	A
i						●
j	●
MAX	0	0	1	0	0	1

i와 j가 일치하므로 i와 j 모두 1증가시킵니다.

	A	B	A	D	C	A	B	A
i							●
j		●
MAX	0	0	1	0	0	1	2

i와 j가 일치하므로 i와 j 모두 1증가시킵니다.

	A	B	A	D	C	A	B	A
i								●
j			●
MAX	0	0	1	0	0	1	2	3

i와 j가 일치합니다. 문자열의 끝이므로 검색을 종료합니다.

 

알고리즘 원리 - KMP 알고리즘

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

최대 일치 길이 테이블을 구하는 알고리즘을 기반으로 수행합니다. 위의 긴 문자열이 검색을 당하는 문자열, 아래가 검색할 문자열입니다.

먼저, i가 1, j가 0일 때, 각각 일치하므로 i와 j를 모두 1증가시킵니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

i가 2, j가 1일 때, 각각 일치하므로 i와 j를 모두 1증가시킵니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

이렇게 증가시키다보면 문자열 ABADCABA까지 모두 일치하여 검색을 1회 성공한 것을 볼 수 있습니다. 그 다음 i를 1증가시키고 j의 위치는 최대 일치 길이 테이블의 j 인덱스에 해당하는 값으로 조정하고 다시 검색을 시작합니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

i가 9, j가 3일 때 각각 B와 D가 일치하지 않습니다. 일치하지 않으면 현재까지 탐색된 문자열(밑줄 친 곳까지가 탐색된 문자열입니다)에 한하여 검색을 당하는 문자열의 접미사와 검색할 문자열의 접두사가 일치하는 한 가장 긴 길이만큼에 해당하는 위치로 j의 위치를 조정합니다. 위 예시에서 AB까지만 일치하므로 j의 위치는 1로 조정됩니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

i가 10, j가 1일 때 각각 C와 B가 일치하지 않습니다. 검색을 당하는 문자열의 접미사와 검색할 문자열의 접두사가 일치하는 것이 없으므로 j의 위치는 0으로 조정됩니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

i가 11, j가 0일 때 각각 일치하므로 i와 j를 모두 1증가시킵니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

i가 12, j가 01일 때 각각 일치하므로 i와 j를 모두 1증가시킵니다.

i

B

A

B

A

D

C

A

B

A

B

C

A

B

A

D

C

A

B

A

j

A

B

A

D

C

A

B

A

이렇게 증가시키다보면 또 하나의 완전히 일치된 문자열을 발견할 수 있습니다. 결과적으로 i가 2번째에서 하나, i가 12번째에서 하나 발견했습니다.

 

알고리즘 구현

// Algorithm Analysis
// KMP 알고리즘 (Knuth-Morris-Pratt)

#include <iostream>
#include <vector>
using namespace std;

// 접두사와 접미사 일치하는 최대 일치 길이 테이블 구하기
vector<int> makeTable(string fs) { // fs : 검색할 문자열
	int fsSize = fs.size();
	vector<int>	table(fsSize, 0); // 0으로 초기화
	int j = 0; 
	for (int i = 1; i < fsSize; i++) {
		// 일치하지 않으면
		while (j > 0 && fs[i] != fs[j]) { 
			j = table[j - 1];
		}
		// 일치하면
		if (fs[i] == fs[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

// ws : 검색을 당하는 문자열, fs : 검색할 문자열
void KMP(string ws, string fs) { 
	vector<int> table = makeTable(fs);
	int wsSize = ws.size();
	int fsSize = fs.size();
	int j = 0;
	for (int i = 0; i < ws.size(); i++) {
		// 일치하지 않는 경우 (단, j > 0)
		while (j > 0 && ws[i] != fs[j]) {
			j = table[j - 1];
		}
		// 일치한 경우
		if (ws[i] == fs[j]) {
			if (j == fsSize - 1) { // 문자열이 완전히 일치하면
				printf("%d번째에서 발견\n", i - fsSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}

int main() {
	string ws = "BABADCABABCABADCABA";
	string fs = "ABADCABA";
	
	// 최대 일치 길이 테이블 결과
	vector<int> table = makeTable(fs);
	for (int i = 0; i < table.size(); i++) {
		printf("%d ", table[i]);
	}
	printf("\n");
	// KMP 수행 결과
	KMP(ws, fs);
}
/*
0 0 1 0 0 1 2 3
2번째에서 발견
12번째에서 발견
*/

 

시간 복잡도 : O(N + M)

KMP 알고리즘의 시간 복잡도는 검색을 당하는 문자열의 길이 + 검색할 문자열의 길이입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.