KMP 알고리즘

KMP(Knuth–Morris–Pratt) 알고리즘은 문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나입니다.

 

이 알고리즘은 패턴과 문자열을 비교해나가다가 틀렸을 때 틀렸다는 사실보다는 틀리기 전에 일치하는 부분이 있었다는 사실에 집중하는 것이 특징입니다.

그러기 위해서 패턴을 통해서 pi배열을 만들고 패턴과 문자열을 비교해나가면서 pi배열을 통해 다시 비교하는 횟수를 줄이는 과정을 거치게 됩니다.

 

이제 과정을 하나씩 설명해 보도록 하겠습니다.

이 설명은 백준1786번 : 찾기 문제를 풀면서 작성하였습니다.

https://www.acmicpc.net/problem/1786

1786번: 찾기

 

pi배열 구하기

---

pi배열을 구하는 정의는 '패턴이 크기가 n인 문자열일 때 인덱스 0~n-1까지 부분 문자열 중 자기 자신의 문자열을 제외하고 접두사와 접미사가 같은 문자열 중 가장 긴 것의 길이'입니다.

무슨 말인지 이해가 되시나요?

제가 공부 할때는 이해가 잘되지 않아서 배열을 구하는 과정을 통해 이해했기 때문에 과정을 보여드리도록 하겠습니다.

 

"AABAAC"라는 패턴이 있습니다.

이 패턴을 자기 자신과 비교하면서 몇 개의 문자가 겹치는지 알아보면 됩니다.

부분 문자열이 A같이 1자리 일 때는 자기 자신의 문자열이 접두사와 접미사가 되기 때문에 pi[0] = 0이 됩니다.

 

그다음인 인덱스 1일 때는 1개가 겹치므로 pi[1] = 1이 됩니다.

코드 상에서는 비교패턴 인덱스가 0이므로 1 증가시켜서 pi[1] = 1이 되지만 편의상 빠르게 이해할 수 있도록 겹치는 문자의 개수로 나타내도록 하겠습니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1
패턴	A	A	B	A	A	C
비교패턴 인덱스		0	1	2	3	4	5
비교 패턴		A	A	B	A	A	C

 

인덱스 2일 때는 겹치지 않습니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1
패턴	A	A	B	A	A	C
비교패턴 인덱스		0	1	2	3	4	5
비교 패턴		A	A	B	A	A	C

이런 경우에는 비교 패턴에서 문자 A의 인덱스가 1이므로 그보다 1 감소한 0을 사용해 pi[0] 값을 가져옵니다.

pi[0] = 0이므로 비교 패턴 인덱스 0의 문자인 A와 B를 비교합니다.

이것 또한 같지 않으므로 pi[2] = 0이 됩니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0
패턴	A	A	B	A	A	C
비교패턴 인덱스			0	1	2	3	4	5
비교 패턴			A	A	B	A	A	C

 

인덱스 3에서는 문자 1개가 같으므로 pi[3] = 1이 됩니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0	1
패턴	A	A	B	A	A	C
비교패턴 인덱스				0	1	2	3	4	5
비교 패턴				A	A	B	A	A	C

 

인덱스 4에서도 문자가 같으므로 AA가 겹치게 되어서 문자 2개가 같습니다.

따라서 pi[4] = 2입니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0	1	2
패턴	A	A	B	A	A	C
비교패턴 인덱스				0	1	2	3	4	5
비교 패턴				A	A	B	A	A	C

 

인덱스 5에서는 문자가 같지 않습니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0	1	2
패턴	A	A	B	A	A	C
비교패턴 인덱스				0	1	2	3	4	5
비교 패턴				A	A	B	A	A	C

앞의 방식대로 진행하면 비교 패턴 인덱스가 2이고 1 감소시키면 1이 됩니다.

pi[1] = 1이므로 인덱스 1의 문자인 A와 비교합니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0	1	2
패턴	A	A	B	A	A	C
비교패턴 인덱스					0	1	3	4	5
비교 패턴					A	A	B	A	A

또 같지 않으므로 pi[0] = 0이므로 패턴 인덱스 0의 문자인 A와 비교합니다.

같지 않으므로 같은 문자가 없게 되어서 pi[5] = 0이 됩니다.

pi 인덱스	0	1	2	3	4	5
pi	0	1	0	1	2	0
패턴	A	A	B	A	A	C
비교패턴 인덱스						0	1	2	3
비교 패턴						A	A	B	A

 

패턴과 문자열 비교

---

이제 패턴과 문자열을 비교할 차례입니다.

비교할 때는 앞의 방식과 똑같이 비교하면 됩니다.

다른 점은 비교하다가 패턴이 발견되면 비교패턴 인덱스의 값을 그대로 pi배열 인덱스로 쓴다는 것입니다.

 

예를 보여드리도록 하겠습니다.

예에서는 패턴을 AABAA로 설정하였습니다.

 

패턴이 발견되었습니다.

이 때 비교 패턴 인덱스는 4이므로 pi[4]를 이용합니다.

pi 인덱스	0	1	2	3	4
pi	0	1	0	1	2
문자열	A	A	B	A	A	C	A	A	B
패턴 인덱스	0	1	2	3	4
비교 패턴	A	A	B	A	A

 

pi[4] = 2이므로 패턴 인덱스 2의 B와 문자열의 다음 문자를 비교하게 됩니다.

이렇게 비교하게 되면 겹친 부분 문자열을 바로 건너뛰어서 빠른 검색을 할 수 있습니다.

pi 인덱스	0	1	2	3	4
pi	0	1	0	1	2
문자열	A	A	B	A	A	C	A	A	B
패턴 인덱스				0	1	2	3	4
비교 패턴				A	A	B	A	A

 

코드

---

 

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

 

https://vvshinevv.tistory.com/2

제가 참고하면서 공부한 링크들입니다.

위의 링크를 통해 공부하고 제 방식대로 코드를 다시 작성해보았습니다.

// baekjoon1786.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

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

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string T,P;
	getline(cin, T);
	getline(cin, P);
	int lenP = P.length(), lenT = T.length();

	//pi에pi 배열 넣기
	vector<int> pi(lenP,0);
	int j = 0;
	for (int i = 1; i < lenP; i++){		
		while (j > 0 && P[i] != P[j])
			j = pi[--j];
		if (P[i] == P[j])
			pi[i] = ++j;
	}

	//P의 처음 인덱스 나타내는 p, 비교하는 인덱스를 나타내는 i, 
	vector<int> ans;
	int k = 0;
	for (int i = 0; i < lenT; i++)
	{
		while (k > 0 && T[i] != P[k])
			k = pi[--k];
		if (T[i] == P[k]) {
			if (k == lenP - 1) {
				ans.push_back(i - lenP + 2);
				k = pi[k];
			}
			else {
				k++;
			}
		}
	}

	cout << ans.size()<<endl;
	for (int i = 0; i < ans.size(); i++){
		cout << ans[i] << " ";
	}
}