KMP【模板】

hexuchen · 2025-02-22 09:34:06 · 算法·理论

void KMP(string a,string b){
    a='-'+a,
    b='-'+b;
    int n=a.size()-1,m=b.size()-1;
    nex[1]=0;
    for(int i=2,j=0;i<=m;i++){
        while(j>0 && b[i]!=b[j+1]){
            j=nex[j];
        }
        if(b[i]==b[j+1]){
            j++;
        }
        nex[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j>0 && b[j+1]!=a[i]){
            j=nex[j];
        }
        if(a[i]==b[j+1]){
            j++;
        }
        if(j==m){
            cout<<i-m+1<<'\n';
            j=nex[j];
        }
    }
}