【算法漫笔】浅谈KMP算法、EXKMP算法
KMP算法
KMP算法主要解决的是字符串匹配问题，即求一个字串在 KKK 原串 SSS 出现的最小位置。我们令 SSS 的长度为 NNN，KKK 的长度为 MMM。
BRUTE-FORCE
首先容易想到在字符串 SSS 中查找子串 KKK 的暴力匹配算法 Brute-Force，它的工作原理很简单，也就是一个一个比对字符，如果不匹配则跳过，直到匹配为止。其缺陷也很显然，如果 KKK 的前 M−1M-1M−1 位都能够匹配但最后一位无法匹配，该算法的时间复杂度可以来到 O(NM)O(NM)O(NM) （如下图）。
这在 N,M≤105N,M \le 10^5N,M≤105 的级别下显然是无法通过的。
优化
那么问题就来了，既然我们已经知道前 M−1M-1M−1 的字符是匹配的，而第 MMM 个字符是不匹配的，那我们能否通过这个信息在下一次匹配的时候跳过部分字符的匹配呢？显然的，我们可以跳过部分匹配，但跳过的字符数量又为多少呢？
NEXT数组
让我们引入一个 nextnextnext 数组，其第 nextinext_inexti 表示在 iii 字符匹配失败时，可以跳过接下来的 nextinext_inexti 次匹配。这个数为多少呢？
我们定义 nextinext_inexti 为模式串 K0,1,…,i−1K_{0,1,\dots,i-1}K0,1,…,i−1 中最长前后缀[1]的长度。
此时容易发现，当匹配到 KjK_jKj 失败时（即 Si≠KjS_i \neq K_jSi =Kj ），我们已经成功匹配了 K0,1,…,j−1K_{0,1,\dots,j-1}K0,1,…,j−1 。根据 nextjnext_jnextj 的定义，K0,1,…,nextj−1K_{0,1,\dots,next_{j}-1}K0,1,…,nextj −1 与 K[j−nextj,…,j−1]K[j-next_j,\dots,j-1]K[j−nextj ,…,j−1] 完全相同，这意味着我们完全可以跳过这些已经匹配的内容。
不难发现，在使用 nextnextnext 数组跳过匹配内容时，所有匹配的内容仅匹配了 111 次，假设我们构造 nextnextnext 数组的时间复杂度为 O(M)O(M)O(M)，那么我们的总时间复杂度为 O(N+M)O(N+M)O(N+M)。现在问题来了，我们怎么在 O(N)O(N)O(N) 的时间下构造 nextnextnext 数组呢？
构造NEXT数组
如何构造 nextnextnext 数组？换句话说，如何计算一段字符串的最长前后缀？
显然我们有暴力计算方法，显然可以用 O(i)O(i)O(i) 的时间复杂度构造一个 nextinext_inexti ，于是乎构造整个 nextnextnext 的时间复杂度就来到了 O(M2)O(M^2)O(M2)，与 Brute-Force 算法无异，显然不行。
此时我们可以使用递推的方式计算，由于我们在计算 nextinext_inexti 时，知道 next1,2,…,i−1next_{1,2,\dots,i-1}next1,2,…,i−1 的全部内容，所以我们实际上可以通过 next1,2,…,i−1next_{1,2,\dots,i-1}next1,2,…,i−1 递推出 nextinext_inexti 。已知 nexti−1next_{i−1}nexti−1 ，看 Ki−1K_{i-1}Ki−1 能否接在 Knexti−1K_{next_i-1}Knexti −1 后面。能就向后继续暴力匹配更长的最长前后缀，否则就回退。如下：
关于递推构造NEXT数组的时间复杂度证明
显然的，iii 未曾回退，且 nextj<jnext_j < jnextj <j，每次匹配成功时 iii 和 jjj 同时加 111，而 iii 总共只增加了 M−1M−1M−1 次，所以 jjj 的总增加次数 ≤M\le M≤M。
由于 jjj 的初始值为 −1-1−1，且 j≥−1j \ge -1j≥−1 恒成立，jjj 的总减小次数 ≤\le≤ 总增加次数 +1≤M+1 \le M+1≤M。
通过以上结论容易得到，全部在 else 分支中的构造时间复杂度为 O(M)O(M)O(M)。
全部在 if 中就更不用说了，显然 iii 会达到 M−2M-2M−2，时间复杂度仍为 O(M)O(M)O(M)。
因此，我们得出结论：构造 nextnextnext 数组的时间复杂度为 O(M)O(M)O(M)。根据前文内容，字符串匹配问题的时间复杂度来到了 O(N+M)O(N+M)O(N+M)，对比 Brute-Force 的 O(N2)O(N^2)O(N2) 快了许多。
模板代码
EXKMP算法
exKMP，即 Z算法，事实上和 KMP 关系并不算太大。
Z数组
让我们引入一个数组 ZZZ，其中 zi=LCPz_i = \operatorname{LCP}zi =LCP[2](S,Si,…,n−1)(S,S_{i, \dots ,n-1})(S,Si,…,n−1 )。特别注意，我们令 Z0=0Z_0=0Z0 =0，这样不仅不会影响算法正确性，反而可以便于我们实现。
构造Z数组
显然可以想到暴力匹配，时间复杂度 O(N2)O(N^2)O(N2)，显然不行。
考虑优化。
我们维护一个区间 [l,r][l,r][l,r]，称为 Z-box，其满足以下性质：
Sl,…,r=S0,…,r−lS_{l,\dots,r}=S_{0,\dots,r-l} Sl,…,r =S0,…,r−l
此时我们已经计算出 Z1,…,Zi−1Z_1, \dots ,Z_{i-1}Z1 ,…,Zi−1 ，现在要计算 ZiZ_{i}Zi ，思考我们在优化构造 nextnextnext 数组时得到的启示，我们如何利用 Z1,…,Zi−1Z_1, \dots ,Z_{i-1}Z1 ,…,Zi−1 的信息构造 ZiZ_iZi 呢？
我们可以先试着分类讨论：
* i>ri > ri>r
显然，iii 在当前的 Z-box 之外，没有可用的已知信息，我们只能从 iii 开始暴力扩展。
此时扩展完成后，更新我们的Z-box：
l=i, r=i+z[i]−1。l = i, \ r = i + z[i] - 1。 l=i, r=i+z[i]−1。
* i≤ri \le ri≤r
iii 在当前的Z-box内部，这意味着我们可以利用已知信息。
尝试令 k=i−lk=i-lk=i−l，则 iii 在Z-box中对应的位置就是 kkk。
由于 Sl,…,r=S0,…,r−lS_{l, \dots ,r}=S_{0, \dots ,r-l}Sl,…,r =S0,…,r−l ，因此 Si,…,rS_{i, \dots ,r}Si,…,r 对应于 Sk,…,r−lS_{k, \dots ,r-l}Sk,…,r−l 。
此时，ZkZ_kZk 已经计算过，它告诉我们 SSS 与从 kkk 开始的后缀的 LCP\operatorname{LCP}LCP 长度。
那么此时如果 Zk<r−i+1Z_k<r-i+1Zk <r−i+1，说明 Sk,…,k+Z[k]−1S_{k ,\dots ,k+Z[k]-1}Sk,…,k+Z[k]−1 完全落在对应的前缀范围内，可以直接取 Zi=ZkZ_i=Z_kZi =Zk 。
反之，如果 Zk≥r−i+1Z_k \ge r-i+1Zk ≥r−i+1：说明匹配可能延伸到Z-box之外，我们无法直接确定。此时，我们令 Zi=r−i+1Z_i=r-i+1Zi =r−i+1，然后从该位置继续进行暴力扩展
扩展完成后，更新Z-box：l=i,r=i+Zi−1l=i,r=i+Z_i-1l=i,r=i+Zi −1。
即：
时间复杂度证明
代码中唯一可能出现时间复杂度的问题是 while 循环。
由于只有 rrr 向右扩展时，while 才会执行。每次成功的匹配都会使 rrr 至少增加 111，而 rrr 的取值范围是 [0,n−1][0,n−1][0,n−1]，因此 while 循环的总执行次数不会超过 nnn。
容易得到总时间复杂度为 O(n)O(n)O(n)
应用
通过构造一些特殊的字符串，使用 exKMP 将会直观的解决部分问题。
例如：我们令字符串 T=S+c+KT=S+c+KT=S+c+K（我们令 SSS 的长度为 NNN，KKK 的长度为 MMM），其中 ccc 为一个在 SSS 和 KKK 中都未出现的字符，例如 ^,&,# 等。
此时根据 ZZZ 函数的定义，如果 Zi=MZ_i=MZi =M，则说明在 SSS 的 i−M−1i-M-1i−M−1 位置找到了一次 SSS 对 KKK 的匹配。其时间复杂度和 KMP 相同为 O(N+M)O(N+M)O(N+M)。
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
zi=LCP(S,S[i…n−1])=max{k∣0≤k≤n−i 且 S[0…k−1]=S[i…i+k−1]}z_i = \operatorname{LCP}(S, S[i \dots n-1]) = \max\{ k \mid 0 \le k \le n-i \ \text{且}\ S[0 \dots k-1] = S[i \dots i+k-1] \} zi =LCP(S,S[i…n−1])=max{k∣0≤k≤n−i 且 S[0…k−1]=S[i…i+k−1]}
通俗来讲即是：从两个字符串的第一个字符开始，最多能连续匹配多少个字符。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 最长前后缀：最长相等的前缀和后缀的长度，也就是字符串 TTT 的前 PPP 个字符和后 PPP 个字符的最大 P≠TlenP \neq T_{len}P=Tlen ，其中 TlenT_{len}Tlen 为 TTT 的长度。 ↩︎
2. LCP，即最长公共前缀长度（Longest Common Prefix），其严格数学定义为： ↩︎
