(알고리즘) 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<< " ";
}
}

댓글

이 블로그의 인기 게시물

(ElasticSearch) 결과에서 순서 정렬

(네트워크)폴링방식 vs 롱 폴링방식

(18장) WebSocekt과 STOMP를 사용하여 메시징하기