KMP

模板库 字符串

地址

$next$ 数组究竟是什么？
即对于当前位置 $pos$ ，模式串在 $[0,next[pos]-1]$ 和$[pos-next[pos],pos-1]$ 的部分完全相同
匹配的复杂度为 $O(n)$ （这里不带证明）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000000+9;
char T[MAXN],P[MAXN];
int next[MAXN];
void GetFail(char *S){
    int len=strlen(S);
    for(int i=1;i<len;i++){
        int loc=next[i];
        while(loc && S[loc]!=S[i]){
            loc=next[loc];
        }
        next[i+1]=(S[loc]==S[i])?loc+1:0;
    }
}
void solve(){
    GetFail(P);
    int len=strlen(T);
    int goal=strlen(P);
    int loc=0;
    for(int i=0;i<len;i++){
        while(loc && T[i]!=P[loc])
            loc=next[loc];
        if(T[i]==P[loc])
            loc++;
        if(loc==goal)
            printf("%d\n",i+1-goal+1);
    }
    for(int i=1;i<=goal;i++)
        printf("%d ",next[i]);
}
int main(){
    scanf("%s%s",T,P);
    solve();
    return 0;
}