功能

KMP 可以快速的处理一个小串 $A$ 在多个长串 $B$ 中是否出现过、出现的次数和每一次出现的位置。其时间复杂度为线性的，是 $O(\lvert A\rvert+\sum\lvert B\rvert)$ 。

实现

如果将下面的两个字符串进行匹配，朴素的办法应该是一位一位的匹配直到出现不同的在将第一个串的起始位置 $+1$ 继续一一匹配，但是这样显然不是最优的。

如果像下图这样效率就可以得到大大提升。

这是因为小串的前缀 $\texttt{ABCABB}$ 与大串的搜索的到的串的后缀 $\texttt{ABCABB}$ 的最长公共字串在除去其本身之后就是 $\texttt{AB}$。从本质上来说，也可以理解为是小串自己在和自己进行匹配。

接下来就是 $nxt$ 数组了，也就是一个辅助完成上面转跳操作的数组。其中如果 $nxt_i=x$，那么有 $\forall j\in [1,x]\cap \mathbb{N}\mid a_j=a_{i-j+1}$。

求 $nxt$ 数组可以直接用双指针从前到后扫一遍，一边扫一遍更新 $nxt$ 数组就可以了。

for(int i=1,j=0;i<=len;i++){
    while(j>0&&b[i+1]!=b[j+1]) j=nxt[j];
    if(b[j+1]==b[i+1]) j++;
    nxt[i+1]=j;
}

对于 $nxt$ 数组的应用，或者说具体求解的过程直接模拟操作就可以了。

for(int i=0,j=0;i<len1;i++){
	while(j>0&&a[i+1]!=b[j+1]) j=nxt[j];
	if(a[i+1]==b[j+1]) j++;
	if(j==len2) // 找到了
}