数据结构（邓俊辉）学习笔记】串 04——KMP算法：查询表

1.制表备查

接下来我们来看看。KMP 算法究竟如何兑现我们刚才所提及的记忆力以及预知力，我们将会看到这种方法非常的便捷与高效，本质上讲，它无非就是构造了一张查询表。

回到我们刚才的问题，在当前这一轮比对，首次失败于 T[i] 与 P[j] 之后，我们应当如何地向后滑动模式串，从而等效地以一个新的 P[j] 来与刚才的 T[i] 对齐，并从这个位置开始继续新一轮的比对。

这里的好消息是，新的这个 P[j] 不仅可以事先确定，而且这个位置仅取决于模式串，而于主串无关。你能看出，为什么与主串没有关系吗？是的，事实上，在这样的一个时刻，主串无非4个部分，也就是文本串的这个前缀以及后缀，再加上在当前这一轮已经匹配的这个子串，以及失配的这个字符。不难看出，这个前缀与后缀对于新的这个 P[j] 字符的确没有任何影响。而这个子串表面上看对它有所影响，但正因为这个子串与模式串的前缀是匹配的，所以与其说这种影响是来自于文本串，不如说最终还是来自于模式串。能否看透这一点，对于我们以下理解KMP 算法至关重要。

既然下一个接替的字符完全取决于模式串自身，由此出发，再进一步地，与其说这个接替的字符是取决于模式串，不如说它取决于被它顶替的此前的那个 P[j]。事实上在一个长度为 m 的模式串中，这样的字符 P[j] 无非 m 种情况。

而 KMP 算法在此处的关键诀窍在于，将所有这 m 种情况事先处理，并且归纳整理为一张查询表。在经过了这样的预处理之后，在后续的各轮比对中，一旦在某一位置 P[j] 处发生失配，我们只需简单地从查询表中取出对应的那一项，并用它来更新此前的 j。

由此可见，这种策略与其说是在借助强大的记忆力，不如说是在事先已经为各种情况准备好了充分的预案。那么基于这种以查询表的形式给出的预案，KMP 算法又是如何具体工作的呢？

2.主算法

现在就来考察 KMP 的主算法，可以看到，无论接口形式还是算法的主体流程，KMP 与我们此前蛮力算法的版本一都颇为类似。是的，它的确是在版本一的基础上略加修改而得。

尽管在形式上这种改动非常的细微，但是在本质上却有巨大的区别。

1. 首先，这里增加了一步预处理，也就是构造出我们刚才所说的那份查询表，我们称之为 next 表。正如我们刚才所言，这个构造过程仅仅取决于模式串，而与文本串没有任何关系，因此是名副其实的预处理；
2. 接下来与蛮力算法一样，我们也需要两个整数 i 和 j ，分别指向文本串和模式串中当前接受比对的那一对字符。
3. 算法的主体循环也基本类似， if 分支完全一样。差异仅仅体现在 else 分支，可以看到 KMP 算法在失配情况下的处理更为简明。具体来说，只需从查询表中取出 j 所对应的那一项，并且用它来替换此前的 j。请注意，在这种情况下，KMP 并没有修改变量 i，也就是说它依然指向文本串中此前刚刚失配的那个字符。

这样的处理过程可以由上面插图来说明。请再次确认，此时情况也就是在当前的这轮比对中，主串的字符 T[i] 与模式串的字符 P[j] 首次发生了失配，在算法中也就对应于那个 else 分支，在这种情况下，如果此前模式串所对应的那个前缀长度为 j，那么接下来 KMP 算法将会把这个前缀替换为长度为 next [j] 的那个新的前缀，并从刚才适配的那个位置出发，继续下一轮比对。

当然，细心的你可能会发现，相对于蛮力算法，这里的 if 分支也并非完全地一样。是的，在对应的逻辑判断式中，这里新增了一个并列的条件，j < 0。关于这个条件的妙用之处，现在来谈，还为时过早，我们不妨暂且将其搁置起来。

3.实例

由上可见，KMP算法的核心就在于那张查询表 next。 在分析这张表的具体原理及其构造过程之前，我们不妨先通过一个实例来切实领会这张表的精妙之处。

考察这个由10个字符所构成的模式串，这里我们直接给出其对应的查询表，请关注其中倒数第三个字符 l，它所对应的秩为 j 等于7，而在查询表中，它所对应的 next 值为3。下面我们就来看看这个表项3所对应的含义及其功能。

假定，这就是主串（chinchi*），如果的确轮到这个表项在发挥作用，那么就意味着在当前这一轮比对中，此前的7个字符都应该是成功的。就是说此时的场景必然是这样（主串上面的模式串），具体来说也就是，模式串中的这个字符 l 与文本串中某个不是 l 的字符比对失败。此时针对这种情况，KMP 算法将会如何处置呢？

为便于对比效果，在处置之前，我不妨先为模式串拍摄一张快照，就像这样（chinchilla）。

现在我们手动来执行一下 KMP 算法

1. 首先，当前的 j 为7指向模式串中的这个字符 l；

2. 接下来， KMP 将在查询表中取出对应的那一项，并用它来更新 j。我们刚才已经看到这个表象，就是3，这就意味着接下来 KMP 将会用秩为3的那个字符，也就是 n， 来取代刚才的 l，并继续与文本串中此前失配的那个字符级对齐，就像这样。

   此时我们不妨为模式串再拍摄一张快照。

对比前后两张快照，我们会发现，其效果等同于模式串向后移动了4个字符。不难看出，这个4是来自于7和3的差。从另一角度来看，这些等效于 KMP 聪明地排除掉了3个不必要的对齐位置。是的，这 3 个位置都是无需对齐的，因为它们都不具备足以对齐的必要条件。比如它们所对应的首字符都不是模式上的首字符 c。而反过来，KMP通过 next 表选择了字符 n，从某种意义上讲是非常合理的。没错，它使得相对于 n 而言的这个前缀，依然与主串是匹配的。 具体来说，c 依然对应于 c，h 依然对应于 h，而 i 也依然对应于 i。

是的，通过这样一个实例，我们的确已经能够感受到 KMP 算法及其中 next 表的精妙之处，但严格上来说，在这种精妙的背后究竟是什么样的原理呢？