[c++] 백준 1786 찾기 ( KMP )

https://www.acmicpc.net/problem/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;
    }
}

패턴이 앞에 존재하지 않으면 (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++;
        }
    }
}

만약 패턴을 다 찾았다면 카운트를 증가시키고 시작위치를 푸쉬한다.

그리고 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;
}