前缀函数与 KMP 算法

• P3375 【模板】KMP字符串匹配

int p[N]={-1};

void kmp(string s1, string s2){
    int i=1, j=0, n1=s1.size(), n2=s2.size();
    while(i<n2 && j<n2){
        if(j==-1 || s2[i]==s2[j]) p[++i]=++j;
        else j=p[j];
    }

    i=0, j=0;
    while(i<n1 && j<n2){
        if(j==-1 || s1[i]==s2[j]) i++, j++;
        else j=p[j];
        if(j==n2){
            printf("%d\n",i-n2+1);
            j=p[j];
        }
    }
}