(알고리즘) KMP알고리즘

KMP알고리즘에서는 부분 일치 테이블을 만들기 위해서 다음과 같은 개념을 알아야 한다.

첫번째는 접두사(prefix)와 접미사(suffix)입니다.

직관적으로 "banana"의 접미사와 접두사를 보면 무엇인지 이해될 것 입니다.

<banana의 접두사>

b

ba

ban

bana

banan

banana

이 6개가 banana의 접두사(prefix) 입니다.

<banana의 접미사>

a

na

ana

nana

anana

banana

이 6개가 banana의 접미사(suffix) 입니다.

두번째로 pi배열 입니다.

pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이

(이때 prefix가 0~i  까지의 부분 문자열과 같으면 안된다.)

무슨 말인지 모르겠죠? 예시를 보면 직관적으로 이해할 수 있을 겁니다.

먼저 문자열 "ABAABAB"의 pi배열을 구해봅시다.

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

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

vector<int> pi;

//부분 테이블 구하는 함수
void getPartialMatch(const string& T)
{
int n = T.size();
pi.resize(n, 0);
int begin = 1, matched = 0;

while (begin + matched<n)
{
if (T[begin + matched] == T[matched]){
++matched;
pi[begin+matched - 1] = matched;
}
else{
if (matched == 0)
++begin;
else{
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
}
//문자열 매칭
vector<int> KMP(const string& T, const string& P)
{
int n = T.size();
int m = P.size();
vector<int> ret;
int begin = 0;
int matched = 0;
while (begin<=n-m)
{
if (T[begin + matched] == P[matched] && matched < m){
++matched;
if (matched == m)
ret.push_back(begin);
}
else{
if (matched == 0)
begin++;
else{
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return ret;
}

int main()
{
string T, P;
FILE* empty; freopen_s(&empty, "ee.txt", "r", stdin);
getline(cin,T);
getline(cin,P);
getPartialMatch(P);
vector<int> ans=KMP(T, P);

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