KMP 알고리즘

Goal

• 여러 문자열 문제에 응용될 수 있는 KMP 알고리즘의 아이디어에 대해 설명할 수 있다.
• KMP 알고리즘에서 사용되는 키워드를 설명할 수 있다.
• KMP 알고리즘을 구현할 수 있다.

---

KMP 알고리즘이란?

문자열 검색 알고리즘으로, 검색 과정에서 불일치가 일어났을 때, 다음으로 검색을 시도할 시작 위치를 빠르게 찾아내는 문자열 검색 최적화 알고리즘이다.

검색 과정에서 얻는 정보를 버리지 않고 활용하는 방법으로, 불일치가 일어났을 때 지금까지 일치한 글자의 수를 이용해 다음 검색을 시도할 위치를 찾아낸다.

(커누스-모리스-프렛(Knuth-Morris-Pratt) 알고리즘, 흔히 KMP 알고리즘이라고 한다)

 

비교하는 두 문자열의 길이가 각각 N과 M일 때,

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

 

접두사, 접미사

부분 일치 테이블(partial match table)

실패 함수(failure function)

burute-force 방법

 

The C library function char *strstr(const char *haystack, const char *needle) function finds the first occurrence of the substring needle in the string haystack. The terminating '\0' characters are not compared.

 

haystack − This is the main C string to be scanned.
needle − This is the small string to be searched with-in haystack string.

 

KMP 알고리즘 구현 코드

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

using namespace std;

void getPartialMatch(const string& N, __out vector<int>& pi)
{
	int n = N.size();
	pi.resize(n, 0);

	int begin = 1, matchCnt = 0;
	while (begin + matchCnt < n)
	{
		if (N[begin + matchCnt] == N[matchCnt])
		{
			++matchCnt;
			pi[begin + matchCnt - 1] = matchCnt;
		}
		else
		{
			if (matchCnt == 0)
			{
				++begin;
			}
			else
			{
				begin += matchCnt - pi[matchCnt - 1];
				matchCnt = pi[matchCnt - 1];
			}
		}
	}
}

vector<int> searchKMP(const string& H, const string& N)
{
	int n = H.size(), m = N.size();
	vector<int> ret;
	if (n <= m)
	{
		return ret;
	}

	vector<int> pi;
	getPartialMatch(N, pi);

	int begin = 0, matchCnt = 0;
	while (begin <= n - m)
	{
		if (matchCnt < m && H[begin + matchCnt] == N[matchCnt])
		{
			++matchCnt;
			if (matchCnt == m)
			{
				ret.push_back(begin);
			}
		}
		else
		{
			if (matchCnt == 0)
			{
				++begin;
			}
			else
			{
				begin += matchCnt - pi[matchCnt - 1];
				matchCnt = pi[matchCnt - 1];
			}
		}
	}

	return ret;
}

int main()
{
	string H, N; // H 문자열에서 N 문자열과 일치하는 값 찾기
	
	cin >> H;
	cin >> N;

	/*
	pi[i] = N[0~i] 문자열에서 접두사도 되고 접미사도 되는 문자열의 최대 길이
	즉, N[0~i]에서 접두사 == 접미사인 최대 길이이다.
	pi를 부분 일치 테이블(partial match table), 또는 실패 함수(failure function) 라고 부르는데,
	몇 개 일치했는지를 기준으로 다음 시작 알려준다.
	*/

	vector<int> matchInfo = searchKMP(H, N);
	for (size_t i = 0; i < matchInfo.size(); i++)
	{
		cout << i+1 << "번 째 일치하는 시작 위치 : " << matchInfo[i] << "\n";
	}

	return 0;
}