P3375 【模板】KMP字符串匹配——kmp算法

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
using namespace std;
const int M=2e6+7;
int f[M],len1,len2;
char s1[M],s2[M];
void getfail(){
    for(int i=1;i<len2;i++){
        int now=f[i];
        while(now&&s2[i]!=s2[now]) now=f[now];
        f[i+1]=(s2[i]==s2[now]?now+1:0);
    }
}
int main(){
    scanf("%s %s",s1,s2);
    len1=strlen(s1); len2=strlen(s2);
    getfail();
    int now=0;
    for(int i=0;i<len1;i++){
        while(now&&s2[now]!=s1[i]) now=f[now];
        if(s2[now]==s1[i]) now++;
        if(now==len2){printf("%d\n",i-now+2); now=f[now];}
    }
    for(int i=1;i<=len2;i++) printf("%d ",f[i]); puts("");
    return 0;
}