题解 | #【模板】KMP字符串匹配#

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
char s[N],p[N];
int ne[N];
int main(){
    scanf("%s%s",s+1,p+1);
    int len1=strlen(s+1);
    int len2=strlen(p+1);
    for(int i=2,j=0;i<=len2;i++){
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[j+1]==p[i]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=len1;i++){
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(p[j+1]==s[i]) j++;
        if(j==len2){
            printf("%d\n",i-len2+1);
            j=ne[j];
        }
    }
    for(int i=1;i<=len2;i++){
       printf("%d ",ne[i]);
    }
    return 0;
}