2.2 字符串查找算法

2.2.1 Knuth-Morris-Pratt算法

Knuth-Morris-Pratt算法简称KMP算法，它的名字是由著名的三位科学家名字组合而成。它是一种高效的字符串查找算法，它的性能高效的原因在于它可以利用字符串匹配过程中失败的信息，从而减少字符串查找比较的次数。

KMP算法借助了一个辅助的结构部分匹配表，部分匹配表是对搜索词分析产生的一个信息表，部分匹配值是某个字或字母的“前缀”和“后缀”的最长共有元素的长度。

在匹配过程中有一个移位规则：移动位数=当前已经匹配的位置-最后一个匹配字的匹配值

对于被匹配的字符串不再存在重复匹配的问题，被搜索字符串都会被依次往下进行匹配，匹配性能会高于传统字符串一一对照的比较方式。

KMP算法是一种典型的字符串模型匹配算法，在查找速度上比传统的字符串好，最坏情况下时间复杂度为O(m+n)，即被搜索字符串与搜索字符串的长度之和。此外，由于它无须回溯访问被搜索的字符串，因此对于文本流中字符串查找可以达到较好的处理，可以一边读一边进行匹配。

2.2.2 Boyer-Moore算法

Boyer-Moore算法简称BM算法，它是在字符串查找的方法中同KMP算法一样重要的字符匹配算法。BM算法相对于KMP算法效果更好，且实现过程更容易理解和实现。

在匹配过程中有一个后移字符规则：后移字符位数=不匹配字符的位置-搜索词中上一次出现的位置

当遇到共同后缀时的移动规则：后移位数=共同后缀的位置-搜索词中上一次出现的位置

在很多文本编辑器中的查找方式都是基于BM算法实现，相对于KMP算法，它的实用性更高，虽然二者的最坏情况下需要的时间为线性的查找时间，但是BM算法的匹配速度比KMP块3~5倍。

2.2.3 Sunday算法

同BM算法类似的还有Sunday算法，它们的思想原理由一定相似性，但是Sunday算法的匹配速度比BM算法还要块。

在Sunday算法的比较过程中最核心的点在于，如果当前匹配失败，则根据被搜索字符串与搜索字符串的对应部分的后面一个字符串作为跳转的依据，如果该字符串不在被搜索字符串中，则直接略过；如果该字符串在搜索字符串中存在，则将该位置与被搜索字符串中的该字符进行对齐，然后从头开始比较。

基于Sunday算法的字符串匹配，相对于其他字符串匹配算法，移除了很多无关的比较操作，在短文本中的匹配或许不够明显，然后从头开始比较。