字符串匹配进阶：BM、Sunday 与 Rabin-Karp

学完朴素匹配和 KMP 之后，很容易产生一个问题：字符串匹配是不是就到此为止了？其实远远没有。KMP 很经典，但它并不是唯一重要的匹配思路。特别是在工程实践和不同输入分布下，人们还发展出了其他非常有代表性的算法，例如 BM、Sunday 和 Rabin-Karp。

这些算法之所以值得单独拿出来讲，不是因为它们只是“更多模板”，而是因为它们体现了三种完全不同的优化方向：

  • BM 尝试让模式串在失配后跳得更远；
  • Sunday 在主串失配后的观察点更靠后一位，规则更简洁；
  • Rabin-Karp 则用哈希把子串比较转化成数值比较。

也就是说，从这里开始，字符串匹配不再只是“怎么少回退”，而是开始出现更多策略层面的差异。理解这些差异，会让你真正意识到：匹配算法优化的核心，从来都不是硬比字符本身，而是如何更聪明地利用结构信息和预处理结果。

一、为什么 KMP 之后还需要其他匹配算法

KMP 的理论复杂度很漂亮，能够做到 O(n + m)，而且主串不回退。但在实际使用中，人们还会继续寻找更适合某些场景的算法，主要原因有几个：

  • 某些场景里希望平均性能更好；
  • 某些算法在字符集较大、模式串较长时跳跃更激进；
  • 有些算法实现思路更贴近工程使用；
  • 有些问题更适合借助哈希而不是字符逐个比较。

所以后续这些算法，不是在否定 KMP，而是在扩展“高效匹配”的策略空间。

二、BM 算法想优化什么

BM，也就是 Boyer-Moore 算法，是经典的高性能字符串匹配算法之一。它最核心的特点是：

不是从模式串左边往右比，而是通常从模式串右端开始比较。

这听起来很反直觉，但正因为从后往前比较，BM 在失配时常常能获得更大的跳跃空间，不必像朴素算法那样只右移一位，也不只像 KMP 那样利用前缀后缀信息。

三、BM 的两大核心思想是什么

BM 的经典跳转通常依赖两个规则。

1. 坏字符规则

如果失配时主串中的某个字符在模式串里出现过，那么模式串可以整体右移，使这个字符与模式串中“最后一次出现它的位置”对齐；如果根本没出现过，就可以直接跳过更多。

2. 好后缀规则

如果模式串尾部已经有一段成功匹配，那么失配后可以尝试让模式串中另一个相同后缀，或者某个前缀，与当前已匹配部分重新对齐。

这两个规则合在一起，通常能让 BM 在很多实际文本中跳得很远。

四、为什么 BM 平均性能常常很好

因为它在很多文本场景里，失配后并不是一格一格挪，而是可以直接跨过一大段不可能匹配的区域。

特别是当：

  • 模式串比较长；
  • 字符集较大；
  • 模式串和主串不太容易局部重复；

BM 的平均表现往往非常亮眼。这也是为什么很多实际字符串搜索实现会参考 BM 家族思想。

五、Sunday 算法为什么常被认为更易理解

Sunday 可以看成是在 BM 思路基础上的一个非常实用、也比较直观的变体。它的核心观察点不是“当前失配字符”，而是：

看当前对齐窗口之后、主串中紧跟着的下一个字符是什么。

然后根据这个字符在模式串中最后出现的位置，决定模式串应该右移多少。

这个规则之所以很受欢迎，是因为：

  • 思想很直观；
  • 实现相对简洁；
  • 平均性能通常也不错。

六、Sunday 的核心直觉是什么

当模式串和主串当前窗口比较失败后，继续下一次尝试时，模式串右移后的新窗口一定会覆盖“当前窗口后面的那个字符”。

于是：

  • 如果这个字符根本不在模式串中；
  • 那当前模式串就可以整体跳过这个字符；
  • 如果它在模式串中，就让模式串中最右边那个相同字符对齐到这里。

也就是说，Sunday 利用的是“下一个必须被窗口覆盖的字符”来指导跳跃。

这让它常常比朴素匹配跳得更大，也比 BM 某些规则更容易讲清楚。

七、Rabin-Karp 的思路为什么完全不同

前面的 BM、Sunday，本质上都还是在研究“怎么更聪明地移动模式串”。而 Rabin-Karp 的路线完全不同，它想做的是：

先把字符串窗口映射成一个哈希值，再比较哈希，而不是每次都逐字符比较。

换句话说，它把“字符串匹配”问题部分转化成了“数值匹配”问题。

八、Rabin-Karp 是怎么工作的

典型思路通常是：

  1. 先计算模式串的哈希值；
  2. 再计算主串当前长度相同窗口的哈希值；
  3. 如果哈希值不同，则一定不匹配；
  4. 如果哈希值相同，则再做一次字符逐个校验，防止哈希冲突；
  5. 窗口右移时，用滚动哈希快速更新下一个窗口的哈希值。

它最大的亮点就在于滚动哈希：

  • 新窗口和旧窗口高度重叠；
  • 不必每次重新算整段哈希；
  • 可以在常数时间更新。

九、Rabin-Karp 适合什么场景

Rabin-Karp 特别适合：

  • 需要做大量窗口比较；
  • 需要做多模式匹配的某些变体；
  • 或者把子串问题转成哈希问题时。

例如：

  • 查重；
  • 子串判等；
  • 文本指纹；
  • 某些重复子串问题。

它和 BM、KMP 这种“逐字符智能匹配”的思路不太一样，更像是一种“先用哈希做粗筛，再用精确比较做确认”的策略。

十、这几种算法怎么比较

1. KMP
  • 最坏复杂度稳定；
  • 适合理论分析；
  • 利用模式串前缀后缀结构。
2. BM
  • 平均性能常常很好；
  • 跳跃更激进；
  • 更适合较长模式串和较大字符集。
3. Sunday
  • 思路简洁；
  • 实现直观；
  • 平均性能也很不错。
4. Rabin-Karp
  • 借助哈希；
  • 特别适合窗口类和多模式相关问题；
  • 需要处理哈希冲突。

所以它们不是谁绝对更强，而是优化角度不同。

十一、为什么字符串匹配会发展出这么多算法

因为字符串本身太特殊了。它兼具：

  • 顺序结构；
  • 局部重复；
  • 前缀后缀结构；
  • 大量窗口重叠；
  • 大量实际文本分布特征。

不同算法就是在利用这些不同特征：

  • KMP 利用前后缀重复；
  • BM 和 Sunday 利用失配后的跳跃机会；
  • Rabin-Karp 利用窗口哈希。

这说明字符串算法最迷人的地方就在于：

同一个问题，可以从完全不同的信息结构出发做优化。

十二、学习这些算法时最容易踩的坑

1. 只记结论，不理解各自优化点

真正重要的是“它到底在利用哪类信息”。

2. 误以为 KMP 就是所有匹配问题的终点

后面还有很多不同场景下更合适的方法。

3. 把 Rabin-Karp 当成绝对精确匹配

哈希值相等不一定完全相等，通常还要二次确认。

4. 不区分最坏复杂度和平均表现

BM / Sunday 很多时候平均很好，但讨论时要分清语境。

总结

字符串匹配进阶算法的重要性，不只是因为它们是 KMP 之后的补充，而是因为它们让你真正看到：同一个匹配问题，可以有多种完全不同的优化视角。真正值得先建立起来的，是这些核心认识：

  • BM 通过坏字符和好后缀规则，让失配后跳跃更远；
  • Sunday 用窗口后一位字符来指导移动，思路更简洁直观；
  • Rabin-Karp 用滚动哈希把窗口比较转成数值比较；
  • 不同算法优化的是不同信息：前缀结构、失配跳跃、哈希筛选；
  • 字符串匹配没有单一万能解，关键在于场景和目标；
  • 真正学会这些算法，不是背几段模板，而是知道它们到底在“少比什么、怎么跳、为什么能跳”。

把这一篇理解透之后，后面再去看 Trie、多模式匹配和搜索系统时，你会更容易把字符串处理看成一整套策略体系，而不是孤立的单个算法。

参考资源：