백준 1786
KMP 알고리즘이란,, 문자열 패턴 매치 알고리즘임
다만 찾는 문자열과 패턴 문자열을 전부 탐색하지 않는다는 점에서 시간복잡도가 급격히 줄어듦.
전체 솔루션을 정리하자면, 실패함수를 구한 후, kmp를 돌려서 패턴 하나를 전부 찾았을 때 카운트를 증가시키고 패턴 시작 위치를 큐에 푸쉬함.
실패함수 찾는 코드
void failfun(){
for(int i=1,j=0; i<p.length(); i++){
while (j>0 && p[i]!=p[j]){
j=fail[j-1];
}
if (p[i]==p[j])
fail[i]=++j;
else
fail[i]=0;
}
}
C++
복사
패턴이 앞에 존재하지 않으면 (j==0) fail[j]=0
패턴과 동일 할 경우 fail[i]=++j를 해준다.
kmp 함수 코드
void kmp(){
for (int i=0,j=0; i<s.length(); i++){
while(j>0 && s[i]!=p[j]){
j=fail[j-1];
}
if(s[i]==p[j]){
if (j == (p.length()-1)){
q.push(i-p.length()+2);
cnt++;
j = fail[j];
}
else
j++;
}
}
}
C++
복사
만약 패턴을 다 찾았다면 카운트를 증가시키고 시작위치를 푸쉬한다.
그리고 j=fail[j]로 패턴을 통째로 넘겨버린다.
+2인 이유는 배열의 첫 인덱스는 0이고, 출력 형식에서 인덱스를 출력하는게 아니라 위치(시작이 1)이기 때문이다.
전체 코드
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
//char s[1000005],p[1000005];
string s,p;
int fail[1000005]={0,},cnt=0;
queue <int> q;
void failfun(){
for(int i=1,j=0; i<p.length(); i++){
while (j>0 && p[i]!=p[j]){
j=fail[j-1];
}
if (p[i]==p[j])
fail[i]=++j;
else
fail[i]=0;
}
}
void kmp(){
for (int i=0,j=0; i<s.length(); i++){
while(j>0 && s[i]!=p[j]){
j=fail[j-1];
}
if(s[i]==p[j]){
if (j == (p.length()-1)){
q.push(i-p.length()+2);
cnt++;
j = fail[j];
}
else
j++;
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
getline(cin,s);
getline(cin,p);
failfun();
kmp();
cout<<cnt<<"\n";
while (!q.empty()){
cout<<q.front()<<" ";
q.pop();
}
return 0;
}
C++
복사
