字符串-KMP算法

字符串（百度百科）

KMP算法（百度百科）

例题：

洛谷P3375

模板代码：

//洛谷P3375
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m;
string s1,s2;
int fail[N];
void getfail(){
    fail[1]=0;
    for(int i=1;i<m;i++){
        int k=fail[i];
        while(k&&s2[k+1]!=s2[i+1]) k=fail[k];
        if(s2[k+1]==s2[i+1]) fail[i+1]=k+1;
        else fail[i+1]=0;
    }
}
void kmp(){
    int now=0;
    for(int i=1;i<=n;i++){
        while(now&&s2[now+1]!=s1[i]) now=fail[now];
        if(s1[i]==s2[now+1]) now++;
        if(now==m) cout<<i-now+1<<endl;
    }
}
int main(){
    cin>>s1>>s2;
    n=s1.size(),m=s2.size();
    s1=" "+s1,s2=" "+s2;
    getfail();
    kmp();
    for(int i=1;i<=m;i++) cout<<fail[i]<<' ';
    return 0;
}