KMP 알고리즘

문자열에 조금 약한 편이라서 한동안 문자열과 관련된 알고리즘에 대해서 공부해보려고 합니다.

 

첫 번째로는 KMP(Knuth-Morris-Pratt) 알고리즘입니다.

KMP는 문자열을 탐색하기 위한 것인데, 어떤 문자열 A와 B가 있을때, 문자열 A에서 B를 포함하고 있는지 탐색하는 것입니다.

 

"This is a pen. I have a pen." 이라는 문장에서 have라는 단어를 찾는다고 한다면, 사람이야 그저 눈으로 훑어보고 바로 어디 있는지 찾을 수 있지만, 컴퓨터로 단순하게 찾는다면 이중for문으로 완전탐색을 통해서 찾을 수 있습니다.

 

완전탐색으로 찾는다면, 시간복잡도는 O(NM)이며, 문자열의 길이가 길어질수록 급격하게 걸리는 시간이 증가해서 시간초과가 발생하기 십상입니다.

 

그러나, KMP 알고리즘은 O(N+N)의 시간복잡도를 가지고 빠르게 찾을 수 있습니다.

 

- Concept

KMP의 컨셉은 다음과 같습니다. (예제는 wiki를 참조하였습니다.)

문자열 S = "ABC ABCDAB ABCDABCDABDE"에서 문자열 W = "ABCDABD"를 찾는다고 해봅시다.(공백도 문자의 일부입니다)

 

그럼 처음에는 이렇게 찾게되겠죠.

그렇다면 우리는 처음 세 글자는 같다는 것을 알게되며, 네 번째 글자가 다르다는 것을 발견합니다.

(여기서 m은 문자열 S의 인덱스, j는 문자열 W의 인덱스입니다.)

 

완전탐색이라면 이제 B를 오른쪽으로 한 칸 옮겨서 비교를 하겠지만, KMP는 위와 같이 비교하지 않습니다.

KMP는 위와 같이 하지 않고, m=3으로 바로 건너뛰어버립니다.

왜냐하면, 이미 처음 세글자를 탐색했고, 탐색한 세글자 중에 S의 첫글자인 A가 없다는 것을 알고 있기 때문입니다. 그래서 m=1에서부터 탐색할 필요가 없으며, m=3으로 건너뛸 수 있습니다.

그리고 m=3인 경우를 비교해보면 처음부터 다르기 때문에 m=4로 이동합니다.

이번에는 W에서 여섯 글자가 일치하다가 마지막 글자가 다릅니다. 

그럼 이번에는 여섯 칸을 건너뛰느냐 ? W와 동일하게 시작하는 문자가 m=8에 위치하고 있으므로, 여섯칸을 뛰어넘으면 탐색이 누락되게 됩니다. 만약 8칸부터 ABCDABD라면 놓치게 되는 것이죠.

따라서, KMP에서는 6칸이 아닌 4칸을 건너뛰게 됩니다.

그리고, W와 동일하게 시작하는 부분은 검사하지 않고 m=10부터 검사합니다. 글자가 다르므로, 글자가 다르기 때문에 다시 처음부터 검색합니다.

W의 처음부터 다시 검사하지만, 다르기 때문에 이번에는 한 칸 이동합니다.

m=11부터 다시 검색을 하면, 아까와 동일하게 여섯 글자가 같고, 마지막 글자가 다르게 됩니다. 

마찬가지로, 6칸이 아닌 4칸을 건너뛰게 되면,

W와 같은 문자열을 찾게 됩니다. 6칸을 건너뛰었으면 찾지 못했겠죠.

 

KMP 알고리즘은 위와 같은 방법으로 탐색을 진행합니다.

 

- Partial match table(failure function)

알고리즘을 구현하기 전에 먼저 필요한 Table이 있습니다. 

바로 failure function 실패 함수인데, 이 값은 mismatch가 발생했을 때, j의 값이 어떻게 변해야하는지를 나타내는 값입니다.

위 예제에서 처음에 세 글자가 일치했을 때, m=1과 j=0을 비교하는 것이 아니라, m=3과 j=0을 비교한 것처럼 말이죠.

따라서 m=3과 j=3을 비교하고, 일치하지 않으니까 j를 0으로 할당해버렸습니다. 즉, failure(j=3) = 0 이기 때문이죠.

그래서 KMP 알고리즘을 수행할 때, 이 table을 결정해주어야 합니다.

 

실패함수는 W의 i번째 글자까지 중에서 일치하는 접두사(prefix)와 접미사(suffix) 중에서 최대의 길이를 값으로 가집니다.

그래서 방금 예제에서 문자열 W의 실패함수는 다음과 같습니다.

i	W[0:i]	failure(i)
0	a	0
1	ab	0
2	abc	0
3	abcd	0
4	abcda	1
5	abcdab	2
6	abcdabd	0

i=4에서 일치하는 접두사/접미사가 a이기 때문에 1이며, i=5에서는 일치하는 접두사/점미사가 ab이기 때문에 2입니다.

 

실패함수는 KMP 아이디어를 사용해서 구할 수 있습니다.

(코드는 위키가 아닌 조금 더 이해하기 쉬운 버전으로 구현했습니다. 따라서, table의 0번째가 -1이 아닌 0이며, KMP 알고리즘에서 일치하지 않는 문자를 만났을 때, failure(j)가 아닌 failure(j-1)의 값으로 j를 업데이트 해줍니다.)

 

while 버전

void kmp_table(string W, vector<int>& T)
{
	int L = W.length();
	T.resize(L, 0);

	int i = 1, j = 0;
	while (i < L)
	{
		while (j > 0 && W[i] != W[j])
			j = T[j - 1];

		if (W[i] == W[j])
			T[i] = ++j;

		i++;
	}
}

for문 버전

void kmp_table(string W, vector<int>& T)
{
	int L = W.length();
	T.resize(L, 0);

	for (int i = 1, j = 0; i < L; i++)
	{
		while (j > 0 && W[i] != W[j])
			j = T[j - 1];

		if (W[i] == W[j])
			T[i] = ++j;
	}
}

 

3. KMP 알고리즘 구현

www.acmicpc.net/problem/1786

1786번: 찾기

위 문제를 통해서, 구현해보도록 하겠습니다.

문자열 T에서 문자열 P가 중간에 몇 번, 어느 위치에서 나타나는지 알아내야 합니다. 결국 문자열 매칭 문제입니다.

설명을 보니, 인덱스가 1부터 시작하므로 결과를 출력할 때 주의해야겠네요.

 

코드는 다음과 같습니다.

int main()
{
	string T, P;
	vector<int> answer;

	getline(cin, T);
	getline(cin, P);

	//get failure function
	vector<int> k_table;
	kmp_table(P, k_table);

	int M = T.length();
	int J = P.length();

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

		if (T[m] == P[j])
		{
			if (j == J - 1)
			{
				//찾은 위치 저장(현재 비교 위치 = m -> 찾은 문자열 끝위치)
				answer.push_back(m - J + 2);

				/* 문자열 끝까지 탐색해야하므로, 동일한 문자열을 찾았을 때,
				   j를 갱신해서 문자열 T 끝까지 탐색한다. */
				j = k_table[j];
			}
			else
				j++;
		}
	}

	printf("%d\n", answer.size());
	for (int i = 0; i < answer.size(); i++)
		printf("%d ", answer[i]);

	return 0;
}

효율을 위해서 19번째줄에 while문을 통해서 비교하는 j 값이 0보다 크다면, 즉, 찾으려는 문자열의 중간부터 할 때, 체크해서 틀리다면 바로 점프시켜주고 있습니다.

그리고 30번째 줄에서는 문자열을 찾았음에도 틀린 문자를 만난 것처럼 j를 갱신해주고 있는데, 문제에서 일치하는 문자열을 전부 찾아야하기 때문에 문자열 끝까지 탐색하기 위해서 j를 갱신하고 있습니다.

 

문자열 탐색 알고리즘으로 KMP, Rabin-Karp, Boyer-Moore 알고리즘을 알아보려고 하는데, 다음에는 Rabin-Karp에 대해서 알아보도록 하겠습니다.