数据结构（邓俊辉）学习笔记】串 08——KMP算法：再改进

1. 美中不足

以上，我们不仅给出了 KMP 算法，同时也证明它的时间复杂度已经达到了渐进意义上的最优，也就是最坏情况也不超过 O(n)。而该算法目前这个版本也绝非完美无缺，接下来我们就会看到在某一方面它依然存在一个细微的瑕疵。要针对这一缺陷，对它再做改进。

为了揭示其中仍然存在的问题，我们从这样一个反例入手。

1. 首先确认对于这样一个模式串，这里给出的的确是他的 next 查询表。与所有情况一样，KMP 算法首先将文本串与模式串在首字符位置对齐，并启动第一轮的字符比对。

   不能看出在经过3次成功的比对之后，算法将首次适配于这一位 1-0 字符。

2. 于是根据算法的流程，接下来我们应该将模式串中的这个字符，替换为它对应的 next 表项所指的那个字符，也就是2号字符。因此接下来等效于将模式串向右侧滑动一个单位，从而按照 next 表的语义，将2号字符与刚才失配的那个文本串字符对齐，并再做一次比对。

3. 城然，这次比对依然会失败。因此接下来我们将去查询2号字符在 next 表中所对应的那一项，也就是1。从效果上看，这依旧等价于将模式串再向右滑动一个单位，从而以1号字符，与文本串中失配的这个字符再次对齐，并再做一次比对。

4. 同样不难看出，这次比对也会以失败返回。因此我们又会继而去查询这个字符，也就是这个字符所对应的 next 表象。并按照这个表现的指示，将0号字符，也就是首字符，与文本串中刚才失配的那个字符对齐，并随即做一次字符的比对。

5. 再一次的，这次比对依然会以失败返回。于是根据算法的逻辑，我们将去查询这个字符，也就是首字符在 next 表中所对应的表象。从而将假想存在的那个通配哨兵与文本串中失配的字符对齐。

6. 当然，既然是通配符，这次比对也必然会成功，从而算法终于得以越过这个位置，而从下一对字符开始继续进行下去。

   当然，我们这里的重点并不在于再次的验证一下 KMP 算法在这种极端情况下的正确性，事实上，我们更加关注的是 KMP 算法在这种情况下的性能表现。

回顾刚才所展示的整个过程，文本串中失配的那个字符先后与模式串中的四个字符进行了比对，才最终在第五个，也就是通配字符处得以匹配。事实上，如果说第一次比对还是有意义的话，那么后续的三次比对实际上都是多余的。

2. 以卵击石

为了更好地理解这一结论，我们不妨来设想这样一个场景。我们可以将这里的字符1比作是一块石头，没错，一块坚硬的石头。而字符 0 则可以想象为是鸡蛋，没错，鸡蛋，而且是一筐鸡蛋。我们算法就犹如一个幼稚的孩子，他想确认一下石头和鸡蛋哪一个更硬，因此作为学习的成本，他需要实际地将二者做一次比对，也就是俗称的以卵击石。

其后果是可想而知的。如果这个孩子还不是十分幼稚的话，经过这样一次实践，他就应该会发现石头要远远地硬于鸡蛋。因此它应该会将框中剩余的那些鸡蛋妥善地保管起来，让它们离这块石头越远越好。

然而，反观 KMP 算法在刚才这个实例中的表现，我们就会发现，它的行为方式居然与一个非常幼稚的孩子极其类似。难道不是这样吗？如果第一次碰撞还勉强可以说是交学费的话，那么后续的一而再，再而三，以致更多次的碰撞的确显得不够聪明。

事实上，从信息的角度来看，我们一开始既然就已经掌握了这个模式串的所有信息，那么自然就应该知道在这个0之前的一系列字符都是0。所以在算法的执行过程中，一旦发现这个0与文本串不相匹配，那自然的就应该知道后续的这些尝试必然都是徒劳的。

尽管不会铸成错误，但毕竟会白白浪费时间。那么 KMP 算法的这个版本问题究竟出在哪呢？

3. 前车之覆

实际上，这个算法的主体流程并没有任何的问题。而在另一方面，我们又注意到，控制 KMP 算法流程走向的，与其说是这个算法本身，不如说是它背后的那张查询表。没错，next 查询表。这张 next 表有既是算法策略的体现者，也是每一个模式串中所蕴含信息的具体承载者。

它简明的刻画了每一个模式串的本质特征，而在当前，它只不过是刻画的还不完全而已。为什么这么讲呢？我还需要从 next 表的语义定义来说起。

比如这个字符 ‘0’ ，它所对应的 next 表项为2，其对应的语义是说：在它所对应的这个长度为3的前缀中，存在一个长度为2的真前缀与同样长度为2的真后缀完全匹配，而且这也是如此的最长匹配。
  ~  
因此在经过相应的滑动之后，这两个部分也就会自然而然地匹配，从而无需对它们重新比对。是的，KMP 在这一方面的确显得非常聪明，因为它充分地利用了我们在此前的比对中所业已获得的信息，这类信息是正面的，因为它们告诉我们相对于当前这个失配字符，它的前缀都是由哪些字符所构成的。

形象地说，这类信息就相当于我们通常所说的经验。然而以往的经历所能告诉我们的，不光有正面的经验，应该有负面的信息，比如教训。是的，在串匹配的计算的过程中，这两方面的信息都是有的。

实际上，相对于当前这个失配的字符，我们不仅能够知道它所对应的前缀是什么，而且反过来我们也应该能知道这个字符不应该是什么，难道这个正是教训吗？很遗憾，KMP 算法目前这个版本还不能及时地汲取这方面的教训，以至于它会一而再，再而三地重复这个错误。

与所有问题一样，一旦你能够定位它，其实也就解决了它的一大半。通过以上的分析，既然我们已经发现 KMP 还不能够吸取教训，那么改进的方法也自然就是使它具有这种能力。

比如一种可行的解决方法就是：在确定各个字符所对应的 next 表项时，除了此前自相似的必要条件，我们还需增加一个新的条件。这个条件与刚才自相似的条件恰好相反，大体而言，自相似条件就等价于说，在这个前缀中存在哪些自相似的特征，而新增补的这个条件恰恰相反，它要指出新的这个字符必须与此前的那个字符不一样，新的这个物体尽管未必比石头要更硬，但是它至少不应该仍然是一枚鸡蛋。

4. 后车之鉴

基于以上分析和结论，我不难得出改进之后的 next 表构造算法。

新的这个版本与此前的版本几乎完全一致。实质的差别仅在于 if 分支中的这个赋值语句。你应该记得在这个分支，我们此前总是简单地用 t 直接地赋予 next 表的下一项，而在这里则附加上了一个新的条件，可以看到在新的版本中，只有在替换的字符与原先的字符本身不等的情况下，我们才沿用以前的方式进行赋值。

而反过来，如果替换的字符与此前那个字符依然相等，我们则要改用另一种方法，具体来说，也就是用更早前所算出的 t 所对应的 next 表象来赋予下一个 next 表象。

各中的原因，你应该能够体会。是的，正如我们此前所举的那个例子，此时的 P[t] 与 P[j] 都是相同的鸡蛋。因此，如果只是简单地进行赋值，那么在后续的匹配过程中就难免会一错再错。

5. 可视对比

在告别 KMP 算法之前，不妨以一种可视的形式将其与蛮力算法作一对比。此前曾因指出，对于串匹配算法的评判与对比，需要分成功和失败两种情况分别进行。因此这里我们不妨只针对失败的情况，对二者的最好与最坏性能做一对比。

在这个图中，我们用这条线（灰色）来表示文本串，它相对而言更长。而模式串的长度 m 则相对更小。

在蛮力算法中，如果我们将文本串固定于此，然后将模式串在各自迭代中的快照记录下来，并按照与文本串相应的对齐位置如此排列，就会得到这样一个相对比较窄，同时非常高的平行四边形。

当然，既然是失败情况，所以每一轮的比对过程都类似。具体来说，都是在经过了一系列的成功比对之后，最终失败于某个位置。而一旦失败之后，算法都会将模式串右移一个字符，并重新开始一轮比对。而且同样的，接下来也会经过一系列的成功比对并最终失败于某个位置。这样的故事会反复地发生，直到最终模式串试图越过文本串的右侧边界。

从这图中我们可以清晰地看到，在每一个对齐位置所消耗的计算成本都可相应的由深色区间的宽度来度量。整个算法累计所消耗的时间应该也就是这些深色区间的宽度总和。那么这一总和变化范围是多大呢？

1. 首先我们注意到有最坏情况：也就在某一个对齐位置，可能会持续地经过 m -1 次成功的比对，而最终失败于第 m 次比对。而整体的最坏情况，莫过于每次都出现这样的最坏情况。关于这一点，我们在此前曾经举过一个具体的实例。
2. 既然在数量级上 m 要小于 n，所以这个平行四边形的高度也就可以直接度量为 n。因此平行四边形的面积也自然就是 n * m，这也是蛮力算法在最坏情况下的性能。
   

再看 KMP 算法，我们同样的可以将所有潜在的和实在的对齐位置按照刚才的方式排列起来，从而同样得到这样一个平行四边形。然而幸运的是，因为 KMP 算法的智能性，它所消耗的时间要远远的小于这个平行四边形的面积。

来看右侧这个局部放大图，在这里我们可以清晰地看到 KMP 的两种优化效果。

1. 你应该记得， KMP 首先能够令模式串得以快速地滑动，也就是说它有可能会直接越过一些潜在的对齐位置，在每一次快速地滑动之后，它也不必继续从头开始比较，而事实上，它只需从刚才失败的那个位置出发，继续开始下一轮的比对。
2. 如果有必要，在经过下一次的快速移动之后，它依然会从新的失败位置开始启动下一轮的比对，以至再下一轮，以及再再下一轮比对。
3. 同样的，在这样的一计算过程中，我们所花费的时间也可以用这些深色的区间来表示，它们的宽度之和，也就给出了 KMP 算法总体的计算时间。

为了统计出所有这些深色区间的宽度之和，我们不妨回到左侧这幅总览图。不难看出，如果将所有这些深色的区间都沿着垂直方向投影到文本串上，我们就会发现任何两段深色的区间，除了在端点处之外，绝不会有任何的重叠。

因此既然文本串的长度为 n，我们也可以由这个图直接推知，整个 KMP 算法所消耗的时间总量也不会超过两倍的 n。对于我们此前的分析完全一致。

在学习过 KMP 算法之后，如果我们回过头来再看看蛮力算法，你或许会对它不屑一顾。是的，就最坏情况下的效率而言，这个算法的确不值一提。然而在此我们也不妨为蛮力算法做些辩护，如果还不是平反的话。事实上，即使是在失败情况下，蛮力算法也有最好的情形，你能想到吗？

是的，在总体失败的情况下，蛮力算法依然需要在每一个对齐位置做一轮比对。然而在最好的情况下，每一步迭代可能只牵涉到常数，甚至只有一次比对。是的，只经过一次比对，就可排除掉一个对齐的位置，应该不难构造出这样的实例。

因此在这种情况下，为了排除掉所有的 O(n) 个对齐位置，蛮力算法所消耗的时间累计也不过是线性。当然，你可能会质疑这种最好情形所发生的概率。事实情况是在通常的情况下，这个概率并不像你想象的那么低。而且随着字符级规模的增大，这个概率也会急速地提高，也就是说在这类情况下，KMP 算法相对于蛮力算法的优势也就不那么明显了。或者反过来等效的，只有在字符集规模相对很小时， KMP 在性能上的优势才能充分得以展示。

你或许已经注意到了，在介绍 KMP 算法的诸多教材中，绝大多数的实例都是基于二进制串。如果你能领会到我们刚才所说的那个现象，你就应该能够更好地理解那些作者的良苦用心了。