1786 찾기

https://www.acmicpc.net/problem/1786

문자열 S에서 패턴 P를 찾는다고 하자. 일반적인 방법으로는 S의 모든 인덱스에 P를 매칭 시켜보는 방법이 있다. 하지만 이 방법으로는 S의 길이를 N, P의 길이를 M이라고 할 때, O(NM)이 걸리게 된다.

하지만 KMP(Knuth-Morris-Pratt) 알고리즘을 이용하면 O(M+N)에 할 수 있다. 먼저, 패턴 P에 대하여 실패 함수 pi[i]를 정의하자. pi[i] = P의 i까지의 부분 문자열에서 prefix와 suffix가 같은 부분 문자열 중에서 가장 긴 것의 길이 (단, prefix가 i까지의 부분 문자열과 같으면 안된다). 실패 함수를 이용하여 문자열 S를 스캔하면서 비교하지 않아도 되는 부분을 효율적으로 건너 뛸 수 있다. KMP의 수행 과정 또한 실패 함수를 만드는 과정과 비슷하다. 따라서 실패 함수를 만드는데 O(M), KMP를 수행하는데 O(N)이 걸려서 총 O(M+N)으로 효율적으로 패턴을 찾을 수 있다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    string s,p;
    getline(cin,s);
    getline(cin,p);
    int n=s.size(),m=p.size();
    vector<int> pi(m);
    pi[0]=0;
    for(int i=1,j=0;i<m;i++)
    {
        while(j>0 && p[i]!=p[j]) j=pi[j-1];
        if(p[i]==p[j]) pi[i]=++j;
        else pi[i]=0;
    }
    vector<int> ans;
    for(int i=0,j=0;i<n;i++)
    {
        while(j>0 && s[i]!=p[j]) j=pi[j-1];
        if(s[i]==p[j])
        {
            if(j==m-1) ans.push_back(i-m+2),j=pi[j];
            else j++;
        }
    }
    cout<<ans.size()<<'\n';
    for(int i : ans) cout<<i<<' ';
    return 0;
}