KMP 알고리즘

blog.naver.com/kks227/220917078260

KMP 알고리즘(Knuth–Morris–Pratt Algorithm) (수정: 2019-09-01)

 

$S[1, i]$ 에서 prefix와 suffix가 같은 최대 길이를 fail[i]라 저장한 전처리 배열을 먼저 만든다.

그 후, 위 그림과 같이 불일치가 발생하였을 때마다, fail에 해당하는 값만큼 건너뛰어, i는 절대 감소하지 않고, j만 이동하도록 만들어 주면 시간복잡도가 $O(N+M)$이 보장된다.

 

fail 함수를 구하는 방법은 단순히 위 알고리즘을 S에서 S를 탐색하는 방향으로 바꾸고, 일치가 발생할 때마다 fail함수에 현재 i위치에 대한 j위치를 기록해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

string SS, TT;
int N, M;
char S[MAXN+10], T[MAXN+10];

int fail[MAXN+10];

int main()
{
	getline(cin, SS);
	getline(cin, TT);

	N=SS.size(); M=TT.size();
	for(int i=1; i<=N; i++) S[i]=SS[i-1];
	for(int i=1; i<=M; i++) T[i]=TT[i-1];

	for(int i=2, j=1; i<=M;)
	{
		if(T[i]!=T[j] || j>M)
		{
			if(j==1) i++;
			else j=fail[j-1]+1;
		}
		else
		{
			fail[i]=j;
			i++; j++;
		}
	}

	vector<int> ans;
	for(int i=1, j=1; i<=N;)
	{
		if(S[i]!=T[j] || j>M)
		{
			if(j==1) i++;
			else j=fail[j-1]+1;
		}
		else
		{
			i++; j++;
			if(j>M) ans.push_back(i-M);
		}
	}
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%d ", it);
}