略谈 KMP

注：本文字符串下标从 0 开始

略谈 KMP

啥是 KMP?

在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称为 KMP 算法）可在一个主文本字符串 S 内查找一个词 W 的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

简而言之，KMP 用来在一个字符串$S$中查找所有子串$W$的位置

比如，在字符串$S=$kmp-is-used-to-ak-ioi 中，子串$W=$i 出现了三次：

kmp-$i$s-used-to-ak-$i$o$i$

而子串$W^{\prime }=$-i 一共出现了两次：

kmp$-i$s-used-to-ak$-i$oi

够简单吧

朴素做法

用两个指针$i,j$表示“当前正在处理$S_i,W_j$”，那么每次判断是否满足$S_i=W_j$，如果是那么
$i=i+1,j=j+1$，处理下一位，否则$i=i-j+1$，$j=0$，相当于起点后移一位重复上述过程。

这种做法的时间复杂度如何呢？事实上，在随机数据测试时，朴素做法可以达到接近于$O(|S|+|W|)$的复杂度，但如果碰上出题人恶意构造的数据，可能被卡成$O(|S||W|)$ $（设想S{=}^{\prime }AAA....AA{B}^{\prime }，W{=}^{\prime }AAA...A^{\prime }，|S|=10^6，|W|=10^5，朴素算法的循环次数将非常可怕）$

优化

考虑当$S_i\ne W_j$时的情况。此时其实有隐含条件：$S_{i-1}=W_{j-1},S_{i-2}=W_{j-2},...,S_{i-j}=W_0$，在朴素做法中，这些信息完全被浪费了

那么我们该怎么利用这些信息呢？很简单，定义数组$Next$（部分讲稿也有叫$kmp$或者$f$的），表示当$S_i\ne W_j$（称作“失配”）时，就直接$j=Next[j]$，相当于模式串$W$向右移动$j-Next[j]$

休息一下，马上回来

参考资料

维基百科
阮一峰的网络日志
《算法竞赛入门经典训练指南》