.NET源码学习 [算法2-数组与字符串的查找与匹配]( 五 ) _生活百科

3. KMP算法（Knuth-Morris-Pratt）【参考文章：漫画：什么是KMP算法？；KMP算法—终于全部弄懂了_June·D的博客-CSDN博客】
回顾一下前两种算法效率不高的原因：在不匹配时，从待匹配串的起始位置重新全部开始匹配；反复计算哈希值，且需要处理哈希冲突的问题。这两种方式可以看作每次将字符串向后一位一位滑动。这样的方式导致了中间存在大量无意义的比较，以及不得不完成的比较，使得效率低下。而KMP就针对这一点进行了优化，其核心在于：在匹配过程中，当不匹配时，对于已匹配好的部分，找到一种规律，将模式串一次性向后滑动很多位，从而提高效率。其中，记不匹配的字符为 “坏字符” ，已匹配的部分为 “好前缀” 。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

于是现在的问题就：如何制定滑动策略？

思考一个应用场景：在一篇文章中匹配某个字符串。那么对于不同的主串，总是用同一个模式串去匹配。如果每针对一个新匹配的主串都要制定新的策略，那么时间复杂度依旧是 n2 级，甚至超过该级数。因此，制定的滑动策略不应该依赖于主串，对于同一个模式串，应当尝试制定同一个滑动策略。即，滑动的策略只与模式串有关。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

接下来进一步思考滑动策略的细节：不匹配时，应当滑动到哪里？

举个例子：

文章插图
首先，把主串和模式串的首位对齐，从左到右对逐个字符进行比较。

文章插图
第一轮，发现前5个字符都是匹配的，第6个字符不匹配，将其标记为坏字符 ‘A’ 。

文章插图
【重难点】
可以发现，在好前缀 “GTGTG” 当中，主串的好前缀的后三个字符 “GTG” 和模式串的前三位字符 “GTG” 是相同的。我们分别把这两部分记作可匹配后缀子串与可匹配前缀子串。在之后的比较中，这两部分一定能够匹配上。并且在这两个部分匹配上之前，一定没有其他可能使得模式串成功匹配的情况，这也为选择最长的子串进行滑动提供了保障。因此，我们直接将模式串后移两位，使得这两部分对齐，并开始下一次比较，省去了中间的无效比较。
同理，如果在好前缀中如果存在多个可匹配后缀子串，那么为了能省区更多的无效比较，我们选择找到最长的子串进行滑动。因此，我们的滑动策略为：在主串的好前缀中，找到最长可匹配后缀子串；在模式串中，找到对应的最长可匹配前缀子串。

文章插图
第二轮，我们直接把模式串向后移动两位，让两个 “GTG” 对齐，继续从刚才主串的坏字符 ‘A’ 开始进行比较。

文章插图
此时，主串的字符 ‘A’ 仍然是坏字符，这时候的匹配前缀缩短成了 “GTG” 。

文章插图
按照第一轮的思路，我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串。此时，剩下字符串 “G” 。

文章插图
第三轮，我们再次把模式串向后移动两位，让两个“G”对齐，继续从刚才主串的坏字符A开始进行比较。
……
小结：整体思路是，在主串的好前缀中寻找最长可匹配后缀子串（在好前缀中，从后往前找），在模式串中寻找对应的最长可匹配前缀子串（在已匹配串中，从前往后找），直接把两者对齐，从而实现模式串的快速滑动。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——