何为 KMP：
KMP算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 $\operatorname{next()}$ 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 $\mathcal{O}(m+n)$。
实现方法：
我们可以发现，KMP 的题目哈希似乎也可以做出来。但是我们可以发现，哈希其实有很多无用功。我们看下图：\
可以发现，在 c 的时候失配(失去匹配)了，但是前面的都符合。如果是哈希，就会像这样匹配：\
很明显，第 $2,4$ 次是无用功，而 KMP 就是为了避免这种无用功。具体是怎么避免的，请往下看。\
我们可以看到上图标红的区域其实是相同的，而第一次符合的就可以与自己本身所对应的先提前比较，避免浪费时间来处理整个的。\
那么怎么处理呢？我们需要用一个 $nxt$ 数组，而我们需要判断的就是，在一个固定的子串中，最长前后缀长度就是可以避免的。\
比如说下图：\aly.tobigirl.com22
我们可以看到这一个字符串 $S$ 所对应的 $nxt$ 数组的数值其实是逐步递增的，那么我们就能得到一个 $\operatorname{getnext}$ 函数，如下：
代码语言：cpp
代码运行次数：0
运行
AI代码解释
void Get_Next(string x){ int i=0,j=-1; nxt[0]=-1; while(i<len2){ if(j==-1||x[i]==x[j]){ i++; j++; nxt[i]=j; } else{ j=nxt[j]; } } }
看完后发现并不难，接下来再附上 KMP 那一段代码，主要是运用 $nxt$ 数组，其实想一想并不难。
代码语言：cpp
代码运行次数：0
运行
AI代码解释
void kmp(string x,string y){ gn(y); int i=0,j=0,ans=0; while(i<len1){ if(j==-1||x[i]==y[j]){ i++; j++; } else{ j=nxt[j]; } if(j==len2){ ans++; j=nxt[j]; } } }
例题：
本期例题较少，以理解为主。题单。
P3375 【模板】KMP：aly.miithub.com11
模板题，没得说。
代码语言：cpp
代码运行次数：0
运行
AI代码解释
#include<bits/stdc++.h> using namespace std; int len1,len2,nxt[1000005]; void gn(string x){ nxt[0]=-1; int i=0,j=-1; while(i<len2){ if(j==-1||x[i]==x[j]){ i++; j++; nxt[i]=j; } else{ j=nxt[j]; } } } void kmp(string x,string y){ gn(y); int i=0,j=0; while(i<len1){ if(j==-1||x[i]==y[j]){ i++; j++; } else{ j=nxt[j]; } if(j==len2){ cout<<i-j+1<<"\n"; j=nxt[j]; } } } int main(){ string x,y; cin>>x>>y; len1=x.size(); len2=y.size(); kmp(x,y); for(int i=1;i<=len2;i++){ cout<<nxt[i]<<" "; } return 0; }
P4824 USACO15FEB Censoring S：
用栈来维护 KMP 的操作，对于后退时不一定要全退，注意就好了。
代码语言：cpp
代码运行次数：0
运行
AI代码解释
#include<bits/stdc++.h> using namespace std; int len1,len2,nxt[1000005]; int st[1000005],top,ss[1000005]; void gn(string x){ nxt[0]=-1; int i=0,j=-1; while(i<len2){ if(j==-1||x[i]==x[j]){ i++; j++; nxt[i]=j; } else{ j=nxt[j]; } } } void kmp(string x,string y){ gn(y); int i=0,j=0; while(i<len1){ if(j==-1||x[i]==y[j]){ st[++top]=i; ss[i]=j; i++; j++; } else{ j=nxt[j]; } if(j==len2-1){ top-=len2; j=ss[st[top]]; } } } int main(){ string x,y; cin>>x>>y; len1=x.size(); len2=y.size(); kmp(x,y); for(int i=1;i<=top;i++){ cout<<x[st[i]]; } return 0; }
P3435 POI 2006 OKR-Periods of Words：
留做练习。
