3.10. 알고리즘 - KMP

KMP

 KMP 알고리즘이란 Knuth–Morris–Pratt이 만든 문자열 검색 알고리즘입니다. 문자열 T와 패턴 P가 주어졌을 때 T에서 P가 나타나는 위치를 효율적으로 탐색할 수 있습니다. 먼저 브루트 포스 방식으로 검색했을 때의 시간 복잡도를 보겠습니다.

브루트 포스

 브루트 포스로 탐색하게 되면 가능한 모든 시작점에서 P크기의 탐색을 진행합니다. 총 T * P번의 비교가 필요합니다. 시간복잡도는 O(TP)가 됩니다. T와 P가 100,000 이상일 경우 탐색하는데 매우 오랜 시간이 걸리게 됩니다. KMP는 이 문제를 O(T)의 시간으로 해결합니다. 핵심 아이디어는 현재까지 탐색한 정보를 이용하여 한번 탐색한 T는 다시 탐색하지 않는다는 것입니다.

실패 함수

 KMP 알고리즘을 사용하기 위해 먼저 실패함수를 정의합니다. 실패함수는 P크기의 배열이고 다음과 같이 정의합니다.

F [i] = max(k) { P [0... k - 1] == P [i - k + 1... i] (0 < k <= i) }

쉽게 말하면 P [0... i]에서 접두사와 접미사가 일치하는 길이의 최댓값입니다. 이때 접두사 및 접미사는 P [0... i]가 될 수 없습니다. 예를 들어보겠습니다. abcabdabcabc라는 문자열 P가 있다고 생각해 보겠습니다. 실패함수는 최장 공통 접두접미사의 길이 이므로 다음과 같이 정의됩니다. 실패함수는 해당 인덱스 다음 위치에서 불일치가 발생했을 때 다음으로 탐색하면 되는 인덱스를 저장하게 됩니다.

index	0	1	2	3	4	5	6	7	...
P	a	b	c	a	b	d	a	b	...
F	0	0	0	1	2	0	1	2	...

 

 실패 함수를 구현하는 과정은 문자열 탐색과 유사합니다. 접두사 부분이 패턴이 되고 현재 탐색 중인 접미사 부분을 텍스트라고 생각할 수 있습니다. 탐색 중인 접미사 부분이 접두사와 일치한다면 양쪽의 인덱스를 증가시키고 불일치한다면 현재 가진 정보를 이용하여 접두사 인덱스만 뒤로 보냅니다. 코드를 먼저 보겠습니다. 

vector<int> Fail(const string& P)
{
	int m = P.size();
	vector<int> fail(m, 0);

	for (int i = 1, j = 0; i < m; ++i)
	{
		while (j > 0 && P[i] != P[j])
			j = fail[j - 1];

		if (P[i] == P[j])
			fail[i] = ++j;
	}

	return fail;
}

 

• i = 접미사 인덱스
• j = 접두사 인덱스

 접두사와 접미사가 일치하는 개수를 저장하는 실패함수는 불일치가 일어났을 때 현재 가지고 있는 정보를 기반으로 탐색을 스킵할 수 있습니다. while문을 보겠습니다. 현재 비교해야 할 접두사 인덱스가 0 이상이고 현재 비교해야 할 접미사 인덱스와 불일치할 때 알 수 있는 정보는 이전 인덱스 까지는 접두사와 접미사가 일치했다는 것입니다. 이전 인덱스의 실패함숫값은 이전 인덱스의 접미사와 접두사가 일치하는 길이를 담고 있으니 실패함숫값을 다음 접두사 인덱스로 사용한다면 일치하는 부분의 탐색은 건너뛸 수 있습니다. 예시를 들어보겠습니다.

 현재 접미사 인덱스 i는 10이고 j는 4인 상황부터 보겠습니다. P [4]와 P [10]은 일치하므로 i와 j를 하나씩 증가시킵니다. P [5]와 P [11]은 일치하지 않습니다. 이때 j의 인덱스가 0보다 크므로 앞에 일치하는 접두사가 있다는 것을 의미합니다. j의 이전 인덱스인 4를 실패함수에 대입해 보면 2라는 값을 얻을 수 있습니다. 이것은 F [0.. 1] 이 F [3.. 4]와 일치한다는 의미입니다. 즉 j를 0으로 돌릴 필요 없이 F [4] 값인 2에서부터 탐색하면 된다는 의미입니다. 

실패함수의 응용

 실패함수를 구현하는 과정은 P 내에서 P의 접두사를 찾는 과정으로 볼 수 있습니다. 그림으로 나타내면 다음과 같습니다.

index	0	1	2	3	4	5	6	7	8
P	a	b	a	c	a	b	a	b	a
P + 1		a	...
P + 2			a	b	...
P + 3				a	...
P + 4					a	b	a	c	...
P + 5						a	...
P + 6							a	b	a
P + 7								a	...
P + 8									a

 

 원본 P 밑에서 새로운 P를 한 칸씩 슬라이딩하면서 비교한다고 생각해 보면 됩니다. P + 4일 때를 보겠습니다. aba까지는 일치했지만 그 뒤가 달랐습니다. 다음 탐색은 P를 두 칸 밀어낸 P + 6입니다. 이런 식으로 중간의 탐색과정을 스킵할 수 있습니다.

 실패함수만 알아도 이 문제를 해결할 수 있습니다. 백준 1701번: Cubeditor

KMP

vector<int> KMP(const string& T, const string& P, const vector<int>& fail)
{
	int n = T.size();
	int m = P.size();
	vector<int> kmp;

	for (int i = 0, j = 0; i < n; ++i)
	{
		while (j > 0 && T[i] != P[j])
		{
			j = fail[j - 1];
		}

		if (T[i] == P[j])
		{
			if (j == m - 1)
			{
				kmp.push_back(i - m + 1);
				j = fail[j];
			}
			else
			{
				++j;
			}
		}
	}

	return kmp;
}

 

 KMP는 실패함수를 구현하는 과정과 유사합니다. 실패함수를 구현할 때는 P 내에서 P의 접두사를 탐색했다면 KMP에서는 T 내에서 P를 탐색합니다. 일치하지 않는다면 효율적으로 스킵하는 방식은 완전히 동일합니다. 유의할 점은 P를 끝까지 찾았다면 다음 P는 겹칠 수도 있으니 j를 또다시 옮겨줘야 한다는 점입니다. 다음 문제는 KMP로 해결할 수 있습니다. 백준 1786번: 찾기

 그림으로 나타내면 다음과 같습니다. 노란색과 파란색의 매칭에 실패했을 때 가운데 부분을 건너뛰고 동일한 빨간 부분부터 탐색할 수 있는 것입니다.

마치며

 오늘은 아무리 봐도 헷갈리는 KMP함수를 알아봤습니다. 실패함수가 가리키는 인덱스가 어떤 것인지, 불일치했을 때 왜 가운데 인덱스는 건너뛰어도 되는 것인지를 생각해 본다면 이해하기가 수월할 것이라고 생각합니다. 감사합니다!