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

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

KMP 알고리즘은 문자열 탐색 알고리즘으로 현존하는 알고리즘 중 가장 빠르고 효율적인 알고리즘입니다.

알고리즘 원리

KMP 알고리즘은 Prefix(접두사), Suffix(접미사)를 활용하여 문자열을 탐색하는 방법입니다.

접두사와 접미사를 destiny로 예시를 들어보겠습니다.

Prefix (접두사)

d
de
des
dest
desti
destin
destiny

Suffix (접미사)

y
ny
iny
tiny
stiny
estiny
destiny

KMP 알고리즘은 탐색할 문자열의 부분 문자열에 대해 가장 긴 Prefix == Suffix인 부분을 새로운 배열(pi라고 하겠습니다)에 저장합니다.

destiny는 동일한 부분이 없으니 AABABA로 예시를 들어보겠습니다.

AABABA의 pi배열

이를 통한 KMP 원리는 다음과 같습니다.

pi배열과 동일한 부분을 넘길 수 있어 시간이 단축된다

기존에 문자열을 처음부터 검색하며 한칸 씩 이동했던 방법과 달리, KMP는 일정했던 크기와 pi배열에 저장된 값에 따라 다음에 탐색을 시작할 위치를 조정하여 탐색시간을 최소화합니다.

KMP 구현

클래스 KMP는 탐색이 진행될 문자열 Findee와 탐색하고 싶은 문자열 Finder를 입력받습니다.

KMP의 MakePI를 통해 KMP 알고리즘을 위한 pi배열을 생성하며, Find를 통해 int형 벡터에 문자열이 발견된 위치들을 저장하여 반환합니다.

//KMP.h
#pragma once
#include <string>
#include <vector>

class KMP
{
public:
	KMP(std::string Findee, std::string Finder)
		: Findee(Findee), Finder(Finder)
	{}

	void MakePI();

	std::vector<int> Find();

private:
	std::string Findee;
	std::string Finder;
	std::vector<int> pi;
};

//KMP.cpp
#include "KMP.h"

void KMP::MakePI()
{
	int s = Finder.length();
	pi.resize(s,0);

	int j = 0;
	for(int i = 1; i < s; i++)
	{
		while (j > 0 && Finder[i] != Finder[j])
			j = pi[j - 1];
		if (Finder[i] == Finder[j])
			pi[i] = ++j;
	}
}

std::vector<int> KMP::Find()
{
	std::vector<int> indexes;

	int findeesize = Findee.length();
	int findersize = Finder.length();
	int j = 0;

	for(int i = 0; i < findeesize; i++)
	{
		while (j > 0 && Findee[i] != Finder[j])
			j = pi[j-1];

		if (Findee[i] == Finder[j])
		{
			if (j == findersize - 1)
			{
				indexes.push_back(i - findersize+1);
				j = pi[j];
			}
			else
				++j;
		}
	}

	return indexes;
}