【笔记】关于 KMP

考前记忆模板。

我们回忆一下 $next$ 数组的含义：

$next[i]$ 表示在 $[1,i-1]$ 内，前缀与后缀相同的部分最长是多长。可以理解为，若第 $i$ 位失配了，至少要往前跳多少步，才可能重新匹配得上。

于是对于匹配串，预处理出它的 $next$ 数组，然后对文本串逐位匹配即可。

#include 
#define maxn 1000001
char p[maxn],t[maxn];
int next[maxn],n,m;
int main(){
    scanf("%s%s",p+1,t+1);
    n=strlen(p+1),m=strlen(t+1);
    for (register int i=2,j=0;i<=m;++i){
        while(j&&t[j+1]!=t[i]) j=next[j];//失配则回到上个匹配的位置；
        if (t[j+1]==t[i]) j++;//匹配就继续向后
        next[i]=j;
    }
    for (register int i=1,j=0;i<=n;++i){
        while(j&&p[i]!=t[j+1]) j=next[j];//失配则回到上个匹配的位置；
        if (t[j+1]==p[i]) j++;//匹配就继续向后
        if (j==m) printf("%d\n",i-m+1),j=next[j];//完整匹配则输出
    }
    for (register int i=1;i<=m;++i)
        printf("%d ",next[i]);
    return 0;
}

后记 不知道为什么我内心一直觉得 NOIp 会考这个算法。。。说不定被我奶中了呢。。。