6.1. KMP 字符串搜索算法¶

这个看似更高效的字符串搜索算法由 D. E. Knuth、J. H. Morris 和 V. R. Pratt 于 20 世纪 70 年代发现，因此被称为 Knuth‑Morris‑Pratt（或 KMP）算法。其搜索效率的关键如下：当在 \(sub\) 的索引 \(p\) 处的特定对齐位置发生不匹配时，我们必须查看 \(sub\) 中索引 \(p\) 之前部分已发生的字符匹配。我们要在 \(sub\) 中紧邻索引 \(p\) 之前的部分寻找 sub 的一个子串，该子串与 \(sub\) 的一个前缀子串相匹配。一旦找到，就可以重新对齐 \(sub\) ，使此前缀子串覆盖原先位于索引 \(p\) 之前的匹配子串。随后，字符逐字比较可以从先前不匹配的位置继续进行。

它的使用需要先对子串 \(sub\) 进行一次遍历，以确定当在位置 \(p\) 发生不匹配时所需的适当重新对齐量。请注意，此确定仅依赖于 \(sub\) ，而与 \(master\) 完全无关。实际上，对于每个索引 \(p\) ，我们要寻找紧邻位置 \(p\) 之前的最长字符序列，该序列需与 \(sub\) 开头的某个序列相匹配。我们必须对此稍作限定，以避免在退化情况下出现问题，即位置 \(p\) 之前的所有字符都相同的情况。当这种情况发生时，我们在位置 \(p ‑ 1\) 重新开始对 sub 的匹配遍历。换句话说，我们专门寻找紧邻索引 \(p\) 之前、长度小于 \(p\) 的最大字符序列，使得该序列与 \(sub\) 开头的某个序列相匹配。对于每个索引 \(p\) ，我们将把这样一个序列的长度存储在一个名为 \(align\) 的数组中。根据 \(align\) 数组的这个定义，下面的幻灯片展示了 KMP 算法如何针对特定的 \(master\) 和 \(sub\) 字符串工作。

前面的幻灯片揭示了 KMP 算法的以下伪代码::

输入：主串、子串、对齐数组 m = 0 s = 0 while((s < sub.length) and (sub.length - s <= master.length - m)):
  if(master[m] == sub[s]): m++, s++ else if(s == 0): m++ else: s = align[s]
if(s == sub.length): return m - sub.length else: return -1

尝试以下练习，看看你能否预测 KMP 算法中某一步的进展。

\(align\) 的创建本身就是一个有趣的算法，需要一些解释。由于 \(align[p]\) 必须小于 \(p\) ，我们首先将 \(align[0]\) 初始化为 ‑1，将 \(align[1]\) 初始化为 0。由于 align 数组是为 \(p\) 的连续值计算的，因此当我们尝试计算 \(align[p]\) 时， \(align[p ‑ 1]\) 已经被计算出来，这使我们能够按照以下幻灯片所示迭代计算 \(align\) 数组。

前面的幻灯片展示了 KMP 算法中计算 \(align\) 数组的如下伪代码::

align[0] = -1 align[1] = 0 L = string.length for(p = 2; p < L; p++):
  q = align[p-1] while((q>= 0) and (string[q] != string[p-1])):
    q = align[q]
  align[p] = q+1

尝试通过以下练习，看看你能否预测此 \(align\) 算法中某一步的进展。

要表明您已完全掌握 KMP 算法的复杂细节，您现在必须成功完成以下三个练习：

1. 练习计算 KMP 算法所需的移位和比较次数

2. 练习：确定具有指定移位次数和比较次数的字符串