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

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

문자열 검색 알고리즘의 하나로, 고지식한 알고리즘을 한 차례 개선할 수 있습니다.

찾을 단어의 접두사와 접미사를 이용하여 탐색횟수를 줄여줍니다.

우선, KMP를 본격적으로 설명하기 전, 고지식한 알고리즘으로 문자열에서 단어를 찾는 경우를 살펴보겠습니다.

고지식한 알고리즘으로 탐색 :: O(MN)

탐색할 문자열 : ABABAABAABAA

찾을 단어 : ABAABA

고지식한 알고리즘은 단어를 한칸씩 이동하면서 문자열을 탐색합니다.

탐색 결과, 찾을 단어의 시작 위치를 7번 변경하여 모든 문자열을 탐색할 수 있었습니다.

이 알고리즘은 단어의 길이가 M이고 문자열의 길이가 N일 때, big-O 표기법으로 O(MN)의 시간복잡도를 갖습니다. 

이제, 같은 문제를 KMP 방식으로 풀어보겠습니다.

KMP 알고리즘으로 탐색, 이해하기 :: O(M+N)

탐색할 문자열 : ABABAABAABAA

찾을 단어 : ABAABA

직관적으로 결론부터 보이자면, 찾을 단어의 시작위치를 4번 변경하여 모든 문자열을 탐색할 수 있었습니다.

어떻게 이런 방법이 가능한지 설명하도록 하겠습니다.

   

맨 처음 탐색을 할 때, sentence[3]의 'B'와 pattern[3] 'A'의 값이 일치하지 않아, pattern을 이동시켜 줘야하는 상황이 옵니다. 

고지식한 알고리즘의 경우, 이 때에 pattern을 한 칸 이동시켜 당연히 일치하지 않을 경우를 탐색하게 되지만,

KMP의 경우 pattern의 접두사와 접미사 일치 길이를 저장했던 정보를 이용하여 이를 건너뛸 수 있습니다.

문자열의 접미사와 단어의 접두사가 일치하는 경우가 있다면, 그 중간을 건너 뛰고 탐색합니다.

탐색이 필요없는 불필요한 경우의 수를 줄여주기 때문에 탐색횟수를 줄일 수 있습니다.

이러한 탐색을 하기 위해서는 찾을 단어의 접두사와 접미사가 일치하는 길이를 저장하는 배열이 필요합니다.

table : 접두사와 접미사가 일치할 때, 그 길이를 저장하는 배열

pattern의 크기를 탐색하며, i번째까지의 길이에서 접두사와 접미사가 같을 경우, 배열에 그 길이를 저장합니다.

이제 배경지식을 공부하였으니 코드를 보면서 이해해 보겠습니다!

고지식한 알고리즘으로 탐색, 코드로 이해하기

makeTable() : 접두사와 접미사가 일치하는 길이를 저장하는 배열을 반환하는 함수

vector<int> makeTable()
{
	int size = (int)pattern.size();
	vector<int> table(size, 0);
	int j = 0;
	for (int i = 1; i < size; i++)
	{
		while (j != 0 && pattern[i] != pattern[j])
		{
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j])
		{
			table[i] = ++j;
		}
	}
	return table;
}

j는 접두사의 마지막 문자를 가리키고, i는 접미사의 마지막 문자를 가리킵니다.

j는 0부터 i는 1부터 시작합니다. 단어의 길이가 1일 때에는 접두사와 접미사가 분리되지 않기 때문에 0을 넣습니다.

while문이 중요한데, 문자가 같지 않을 때에는 접두사의 마지막 부분을 그 전의 일치했던 부분으로 돌아가며 찾습니다.

KMP() :: 문자열에서 찾는 단어의 일치 횟수를 반환하는 함수 

int kmp()
{
	vector<int>t = makeTable();
	int ssize = (int)sentence.size();
	int psize = (int)pattern.size();
	int ans = 0;
	int j = 0;
	for (int i = 0; i < ssize; i++)
	{
		while (j != 0 && pattern[j] != sentence[i])
		{
			j = t[j - 1];
		}
		if (pattern[j] == sentence[i])
		{
			if (j == psize - 1)
			{
				ans++;
				j = t[j];
			}
			else
				j++;
		}
	}
	return ans;
}

kmp함수는 makeTable함수와 유사한 형태를 띕니다.

다른 점은 문자열과 단어 모두 처음부터 탐색을 시작하는 것과

단어의 길이만큼 모두 탐색하였을 때, 단어의 마지막 위치를 접미사와 일치하는 접두사의 위치로 바꿔주는 것입니다.

마지막으로 제가 풀었던 SW Expert Academy 1213. String 문제의 전체 코드입니다.

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

int num, ans;
string sentence, pattern;

vector<int> makeTable()
{
	int size = (int)pattern.size();
	vector<int> table(size, 0);

	int j = 0;
	for (int i = 1; i < size; i++)
	{
		while (j != 0 && pattern[i] != pattern[j])
		{
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j])
		{
			table[i] = ++j;
		}
	}
	return table;
}
int kmp()
{
	vector<int>t = makeTable();
	int ssize = (int)sentence.size();
	int psize = (int)pattern.size();
	int ans = 0;
	int j = 0;
	for (int i = 0; i < ssize; i++)
	{
		while (j != 0 && pattern[j] != sentence[i])
		{
			j = t[j - 1];
		}
		if (pattern[j] == sentence[i])
		{
			if (j == psize - 1)
			{
				ans++;
				j = t[j];
			}
			else
				j++;
		}
	}
	return ans;
}
int main()
{
	int T = 10;
	while (T--)
	{
		cin >> num;
		cin >> pattern;
		cin >> sentence;
		ans = kmp();

		cout << '#' << num << ' ' << ans << '\n';
	}

	return 0;
}

설명이 허술했지만, 복습하고 나중에 찾아볼 겸 작성하였습니다.

누군가에게는 도움이 되길 바랍니다...ㅠ!