【笔记】关于 KMP

Zepto -

考前记忆模板。

我们回忆一下 $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="=m)" printf("%d\n",i-m+1),j="next[j];//完整匹配则输出" printf("%d ",next[i]); return 0; }< code>

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