KMP (Knuth Morris Partt Algorithm) - 문자열 탐색

원인은 백준 1786 문제.

 

문제의 답은 간단하다.

본문 내에 탐색하고자 하는 문자의 개수와 위치를 출력 하는 것

 

본문의 글자를 모두 비교하면 되겠다는 단순한 생각으로 접근 했을 때의 결과는.

 

당연히 시간 초과.. 무려 O(mn)의 시간으로...

시간 제한을 체크하지 않은 내 실수였다.

 

그래서 방향을 다시 잡고 고민을 해보았지만, 쉽게 떠오르는 방법은 없었다.2~3시간 고민 이후, 문자열 탐색에 대한 알고리즘을 찾아보기 시작했다.가장 쉽게 접한 알고리즘이 KMP 알고리즘이다.

 

KMP의 구조는 간단하지만, 왜 이렇게 하는게 정상적으로 나오게 되는지에 대한 이해를 하는 시간에만 2일이 걸렸다.

 

 

KMP는 최대 O(m+2n)으로 O(m+n)으로 나타낼 수 있다.

주요 원리는 탐색하려는 문자열에 대한 재탐색 비용을 줄이는 데에 있다.

 

문자열 검색에 있어서 가장 많은 시간을 소모하는 것은, 탐색하는 문자열을 Index마다 비교해야 하는 비용이다.문자열을 비교하는 것을 본문 한번 진행할 때에 끝낼 수 있다면, 가장 짧게 탐색하는 시간에서 나온 알고리즘이다.

 

그래서 최소 탐색 비용인 O(m)을 제외하고, m번만큼 탐색하는 동안 반복을 줄이기 위해 문자열에 대한 분석을 한다.분석의 이유는 다음 탐색 시작 지점을 단축하기 위함이다.

 

다음 탐색 지점을 단축한다는 의미는, 문장 내에 내가 시작해야 하는 위치를 미리 계산한다.그렇다면 어떤 기준으로 탐색 위치를 계산해야 하는가?

 

접두사(Prefix)와 접미사(Prefix)가 같은 지점을 찾아 계산하는 것이다.

 

탐색하려는 문자 ABAABA 가 있을 때, 해당 문자열의 시작 ~ 끝 지점까지 문자열을 분리하여, 각 각의 시작 위치를 탐색하는 방식이다.

 

String	Prefix ~ Suffix	Index
A	A	0
AB	AB	0
ABA	ABA	1
ABAA	ABAA	1
ABAAB	ABAAB	2
ABAABA	ABAABA	3

위처럼 계산을 하는 이유는, 만약 String 열의 글자수만큼 같다라는 것을 안다면, 해당 문자열 내에서의 비교를 없앨 수 있다.

 

A B A A B C A A B A A B A

A B A A B A

 

 

위와 같은 비교가 있을 때, 위의 표에 따르면 ABAAB의 문자열에 해당하는 Index 값은 2 이다.그렇다면 틀린 지점에서 뒤의 2개의 문자는 같다라는 것을 알 수 있으므로, 틀린 지점에서부터 앞의 2개는 비교할 필요가 없고, 3번째 글자부터 비교를 하면 된다.

 

A B A A B C A A B A A B A

          A B A A B A

 

마찬가지로 AB 문자열에 해당하는 값은 0 이므로, 틀린 지점부터 다시 비교를 시작할 수 있다.

 

이러한 방식은 비교하는 Index를 단축시키는 효과를 가져오므로, 최소한의 비교인 m번으로 탐색을 마칠 수 있다.

하지만 위의 접두사와 접미사에 대한 계산을 미리 해야하므로, 2n번의 계산을 미리 하는 과정을 거치게 되므로, O(m+n)으로 나타낼 수 있는 알고리즘이 된다.

 

 

알고리즘의 기본 개요는 위와 같고, 코드로 작성하게 되면 생각보다 어려운 난관에 봉착하게 되었다.

문자열을 비교하는 방식은 어렵지 않으나, 접두사와 접미사를 계산하는 데에 있어서 최소한의 시간을 써야 하기 때문이다.

 

처음에는 탐색 문자열을 가볍게 접근하여 n x n으로 계산하였지만, 탐색 문자열이 길 수도 있기 때문에, O(m+n)의 효과를 보려면 1번의 문자열 반복으로 해결하는 것이 이상적이다.

 

vector<int> GenerateFixed(string s)
{
	vector<int> fixed(s.size(), 0);

	for (int i = 1, j = 0; i < (int)s.size(); ++i)
	{
		while (j > 0 && s[i] != s[j])
			j = fixed[j - 1];

		if (s[i] == s[j])
			fixed[i] = ++j;
	}

	return fixed;
}

결과만을 보면 의외로 간단한 코드이지만, 해당 로직을 이해하는 과정은 쉽지 않았다.

 

먼저 i = 0 인 경우는 무조건 다음 글자부터 비교해야 하므로 0번째에 대한 계산을 스킵한 상태로 진행된다.

i는 마지막 글자, j는 시작 글자를 비교하게 될 위치이다.

 

A B A A B A

글자를 비교할 때, 로직적으로는 아래와 같다.

 

A B

 j  i

→ 글자가 다르므로, 따로 저장할 값이 존재하지 않는다.

 

A B A

 j      i

→ 글자가 같으므로, 현재 j 위치값의 +1 값을 Index로 저장한다.

 

A B A A

     j      i

→ 이전의 비교에서 j가 증가하였으나, i != j 이므로 글자를 비교하기 전에 i와 같은 글자를 찾을 때까지 0번째 문자로 돌아간다.

A B A A

 j          i

→ i와 j가 같으므로 현재 j의 위치값 + 1의 값인 1이 Index가 된다.

 

A B A A B

     j          i

→ 증가된 j값의 문자와 i값의 글자가 같으므로, 현재 j의 위치값 + 1의 값인 2가 Index가 된다.

추가적인 비교가 필요하지 않은 이유는, 이전의 위치인 j - 1, i - 1위 위치는 이전에 같다는 정보가 j의 위치에서 알 수 있기 때문이다.

필자는 해당 부분이 이해가 쉽지 않았다.

접두사와 접미사를 찾는 것이기 때문에, j가 증가한 시점에서 i도 증가가 될 예정이기 때문에, 이전 비교에 이어서 다음 글자를 지속적으로 확인 할 수 있기 때문이다.

 

A B A A B A

         j          i

→ 증가된 j값의 문자와 i값의 글자가 같으므로, 현재 j의 위치값 + 1의 값인 3이 Index가 된다.

 

위의 과정을 통해 n번의 비교만으로 탐색에 필요한 Index들을 정의할 수 있다.

 

그렇다면 왜 이전의 계산된 j-1번 째 문자열이 j로 들어갈 필요가 있는 것인가? 여기가 특히 이해하기 여러웠다...

while (j > 0 && s[i] != s[j])
	j = fixed[j - 1];

이유는 j의 위치에 따라 이전에 비교된 문자열로 탐색을 진행해야 하는 경우 때문이다.

이는 다음 탐색 지역을 찾는 것을 최소화 하기 위한 방법이다.

 

A B A B A B A B

위의 문자열을 미리 계산할 때, ABABAB의 값을 2가 된다.

ABABAB

Prefix는 빨강 + 초록

Suffix는 초록 + 노랑 으로 나타내기 때문

 

위의 계산된 값으로 비교를 진행해야 된다면, 

 

A B A B A B A C A A B

A B A B A B C B

 

의 다음 비교는 

 

A B A B A B A C A A B

             A B A B A B C B

 

로 진행하게 된다.

하지만 위의 진행보다 조금 더 단축하려면, 

 

A B A B A B A C A A B

       A B A B A B C B

 

해당 위치부터 진행하는 것이다.

위의 코드는 이 부분을 위해 존재한다.

 

미리 계산하는 단계에서 반복 횟수를 늘리지만, 실제로 해당 반복 횟수를 문자 탐색에서 사용하는 것이 더 많이 늘어나기 때문에 사전에 미리 계산하는 것이 효율적이다.

 

겨우 겨우 통과한 백준 코드이다..

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> GenerateFixed(string s)
{
	vector<int> fixed(s.size(), 0);

	for (int i = 1, j = 0; i < (int)s.size(); ++i)
	{
		while (j > 0 && s[i] != s[j])
		{
			j = fixed[j - 1];
		}

		if (s[i] == s[j])
		{
			fixed[i] = ++j;
		}
	}

	return fixed;
}

int main()
{
	string T;
	string P;

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

	vector<int> fixed = GenerateFixed(P);

	vector<int> FindIndex;

	for (int i = 0, j = 0; i < T.size(); ++i)
	{
		while (j > 0 && T[i] != P[j])
			j = fixed[j - 1];

		if (T[i] == P[j])
		{
			if (j == P.size() - 1)
			{
				FindIndex.push_back((i + 1) - j);

				j = fixed[j];
			}
			else
				++j;
		}
	}

	cout << FindIndex.size() << endl;
	for (vector<int>::iterator iter = FindIndex.begin(); iter != FindIndex.end(); ++iter)
	{
		cout << *iter << " ";
	}

	return 0;
}