图文并茂！字符串匹配之Sunday、KMP和BM算法入门级讲解

全网最幼稚园级别的字符串匹配算法科普，手把手带你辨别字符串匹配的花样套路。

字符串的模式匹配是NLP领域的基础任务，可以帮助我们在大量的文本内容中快速找到需要的文本信息，比如在文章中搜索关键词的位置和数量。

字符串模式匹配问题按照具体任务类型可以分为单模式匹配和多模式匹配。单模式匹配是指匹配模板为单个字符串，即从待匹配字符串 (string) 中找出匹配模板 (pattern)，比如著名的KMP算法和BM算法等等；而多模式匹配则表示匹配模板为多个字符串组成的模板集合，即从 中找到匹配模板集合 的所有匹配结果，比如AC自动机等等。

本文主要介绍单模式匹配的常见算法：

• 朴素查找算法 Naïve String Search Algorithm
• Sunday算法 Sunday Algorithm
• KMP算法 Knuth–Morris–Pratt Algorithm
• BM算法 Boyer–Moore Algorithm

1 朴素查找算法

朴素查找算法又被称为暴力算法（Brutal Force），是待匹配字符串 和模板 逐个字符依次进行匹配的简单粗暴算法。这种算法中，模板 先与 左侧对齐，从左往右逐位与 相应位置的字符比对，一旦失配， 右移一位，再重复上述步骤，直至完全找到匹配的部分，否则不存在相应的匹配。

如下图所示，蓝色表示匹配，红色表示失配。 与 从左往右逐位比对，失配后右移1位，连续右移4位后匹配成功。

朴素算法的思路简单，完全没有考察pattern本身的特点，没有考察匹配部分和未匹配部分的特点，进行了很多完全没有必要的比对。

下面要介绍的算法，会通过研究模板和待匹配字符串的特点，跳过一些不必要的比较，让 每次可以多走几步。

2 Sunday算法

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配算法，它比后面要介绍的KMP算法和BM算法都要晚提出。不过其逻辑和处理方式比后二者要更简单清晰，故提前介绍。

Sunday算法会提前记录 的组成和每种字符在 中最右出现的位置，比如 : "abcab"，每种字符在模板中的最靠右的位置为{'a':3, 'b':4, 'c':2}。

在每一次的比较中，一旦出现失配，算法会去看 中在当前匹配段后一位的字符 ，找到这个字符在 中最右出现的位置，并与其对齐，如果在 中没有对应的字符 ，则直接右移跳过整段的匹配段。

看下面的例子：

与 在当前位置失配，直接去看 在当前匹配段（灰色线框）的后一个字符 为'b'（绿色方框），并在 中找到最靠右的'b'， 右移1步至两个'b'对齐（下图蓝色线框）。

新的位置仍然失配， 在该匹配段的后一个字符 为'c'，同样的操作，将 右移3位，使 中的'c'与 中的这个'c'对齐，成功匹配。

可以看到，巧妙地利用字符串的特点可以有效减少匹配的次数，提高匹配效率。

3 KMP算法

Knuth–Morris–Pratt Algorithm是以3个发明者的名字命名的字符串匹配算法，类似的，它也通过右移 从左往右依次匹配 。

该算法需要提前计算 部分匹配值表PMT（Partial Matching Table），其中元素为 每一个前缀子串的所有前缀和后缀的最大重叠串的长度。我们先来看看PMT表格。

对于字符串 :"abcab"，其PMT表格为：

可以看到表格中PMT[3]=1，即前缀子串"abca"的PMT值为1，具体的计算过程如下：

查看的前缀子串"abca"，这个子串的所有的前缀和后缀（不包括自身）为：

• 所有前缀：{"a", "ab", "abc"}
• 所有后缀：{"a", "ca", "bca"}

前缀和后缀的最大重叠的字符串为"a"，故其PMT值为1。

下面我们来看，怎么在具体的例子中应用PMT：

图中，该匹配段在最后一个字符失配，已经匹配成功的子串 为"abca"，根据上表，PMT[3]=1。右移的位数为已匹配的前缀子串（即 ）的长度-PMT值，此处需要右移 步。可以看到， 的前缀"a"移动到了后缀"a"之前所在的位置上。

右移3位之后，匹配部分 为"a"，长度为1，此时PMT[0]=0，故右移 位，成功匹配。

可以看到，计算PMT的主要目的，是通过研究模板 自身的特性，如果成功匹配部分 的前缀和后缀相同，就可以直接将相应前缀移动到对应的后缀上去，减少移动步数。

4 BM算法

Boyer-Moore算法是于1977年由德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授提出。 右移去匹配 ，但与上文的方法不同的是，这里是从右往左依次匹配。这种算法将会引入2种不同的规则。

4.1 坏字符规则 Bad-Character Heuristics

对 中与 的失配字符 ，如果 中有 ，则移动 ，使其中最靠右的 与 中的 对齐。

上图中 中与 失配的字符 为'a'， 右移1位，让 中最靠右的'a'和 中失配的'a'对齐（下图蓝色线框）。

上图新的位置失配字符 为'a'，继续使用坏字符规则，让 中最靠右的'a'和 中失配的'a'对齐，发现此时 需要左移1位。

可以看到，仅仅使用坏字符规则， 可能还需要左移走回头路，这是不可以接受的，此时需要结合另一个规则一起使用：好后缀规则。

4.2 好后缀规则 Good-Suffix Heuristics

对成功匹配的后缀子串 ，考查：

• 如果 中还存在其他完整的 ，则将 右移，使 中的 与 中除了句末的 之外最靠右的 对齐
• 如果 中不存在其他完整的 ，则如果 的后缀中有和 的前缀相同的部分，则右移 ，使 的前缀与 的后缀对齐。

在刚才的匹配中，坏字符规则后的中间步结果为：

当前匹配成功的子串 为"ab"，在 中还存在一个"ab"子串，则右移 ，让前一个位置的"ab"与当前 中的"ab"对齐，成功匹配。

为了解释好后缀规则的第2种情况，这里引入一个新的例子来介绍：

当前匹配成功的子串 为"ba"，在这个 中不存在另一个"ba"子串，则查看 的后缀中是否有与 的前缀相同的部分，发现存在相同子串"a"，则右移 ，使得两个"a"对齐，并成功匹配。

以上即对好后缀规则的两种情况的介绍。

在应用中，坏字符和好后缀规则会分别给出右移距离，选择较大的那个右移距离，不允许出现走回头路的情况发生。

可以看到，BM算法中，坏字符规则类似于Sunday算法（实际上是Sunday算法在BM的基础上的改进），好后缀规则类似于KMP算法。这些算法的原理和规则实际上都是利用字符串自身的特点和匹配时的特征，使可以跳过确定无法匹配成功的位置，从而加快搜索的速度。

参考文献

1. Sunday 字符串匹配算法(C++实现) \ www.cnblogs.com/lyc94620/p/11420092.html
2. 字符串匹配的Boyer-Moore算法 \ https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
3. 字符串匹配的KMP算法 \ https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
4. 算法之「字符串匹配算法」\ https://juejin.im/post/5ccef225e51d456e4b3c6f31
5. 浅谈字符串匹配 \ https://blog.brickgao.com/2015/08/08/string-searching-algorithm/