Boyer Moore 算法（一）：原理

Boyer Moore 算法是比较常见、通用的字符串匹配算法。它于 1977 年在Boyer 等人的论文^[1] 被提出。目前，C++ 语言的标准库实现的就是 BM 字符串匹配算法。

问题

给定字符串 和 ，分别作为目标和模式串，求 在 中的出现位置（下文称出现位置为 shift，即模式串第一个字符所处位置在目标串的下标）。

记从 下标开始的长度为 的字符串 的子串为 ，记从 下标开始到 下标结束的字符串 的子串为

算法原理

BM 算法基于的 Brute Force 思路如下：

对于所有的 shift ， 是否和 相同。

从 shift 开始；对于每一个 shift ，我们从最右侧的 和 开始，向左逐字符匹配。直到匹配完成或在某一位置失配，进入 的 shift。

注意，很大的不同：对每一个 shift，从右往左匹配模式串。

这样的 Brute Force 算法的复杂度是 的，最坏情况是在每个位置都匹配成功。

优化的整体思路，是从最坏的情况，即每个 shift 都能匹配上很多的时候，因此优化方向就是：

1. 减少需要考虑的 shift 数量。
2. 减少在考虑某个 shift 时，需要进行的比较。

以下的两个优化聚焦在如何减少需要考虑的 shift 的数量，具体方法是增大可能的 。换句话说，在一次 shift 为 的匹配结束（成功或在某个位置失配）之后，让 shift 能够多往后移动一些，而不是仅仅从 移动到 。

Bad Character 优化

在模式串的 位置失配的时候，我们在目标串的 位置会遇到一个“Bad Character”。因为这个字符在目标串中出现，但在模式串这个位置没有出现，所以我们认为这个字符可能在模式串中比较少。

极端情况是，这个字符根本没有在模式串中出现。这样的话，不可能在目标串包含 的区间内匹配上模式串。因此，我们可以将新的 直接设置成 ， 。

一般情况是，这个字符在模式串中出现了，出现在 。我们希望能把 和 对齐，这样的话 ，也就是 。我们要选择所有这样的优化中 最小的，防止跳过可能能够匹配的 shift位置。这样的话，我们希望找到最右侧的字符 。

我们记 ，其中

意义就是：如果在模式串匹配到 时失配，且 ，那么 。

值得注意的是，这样的 有可能小于 0 。

在实际实现中，由于只有在匹配运行时才会知道 的取值，所以实现中 的计算实际上是计算字符 对应的 ，在匹配时算出 。

Good Suffix 优化

思路仍然是：试图减少需要考虑的 shift 的数量。假如我们在 shift 为 的时候进行了匹配较多之后才失配，虽然我们耗费了很多时间而且一无所获，但是匹配的过程让我们对于目标串有了较多的了解。直觉上来说，利用好对于模式串预处理的机会，我们是有可能排除掉一些对 shift 位置的考虑的。对我们来说，只和模式串有关的性质是更好的。

假如此时 shift 为 ，在 处与 失配。此时可以知道， ，两串中长度为 的子串完全一致。

假如我们接下来将 shift 增大 ，即 ，那么：

在 shift 为 时能够匹配成功，也就是 ；在 处截断后部，得到其必要条件是： 。

如果 ，那么结合之前在 shift 为 时候的匹配，并对以上的必要条件截断一部分（仍然保留必要性！），可以得到仅与模式串有关的条件：

除此之外，因为在目标串在 失配，新的 shift 位置想要匹配上还必须有 。这意味着这是从 向左侧延伸的，和从 向左侧延伸的，两个字符串的最长匹配。

如果 ，同理可以得到必要条件：

我们发现，由于模式从 向左侧延伸的串已经到了头，下面的这条依然成立。这是很重要的性质，将被我们用来高效实现这个算法。

"这是模式串从 向左侧延伸的，和从 向左侧延伸的，两个子串的最长匹配。"

我们要保证不能跳得太多，以至于跳过了可能匹配上的 shift，因此我们要在由上述的必要条件确定的一个可能匹配的 shift 的超集上选取一个最小值，作为我们这一次对 shift 的改变。

形式化地来说，我们构造 ，其中 ，定义为:

事实上，如果 有元素，一定会比 里面的任意元素都要小。

在实现上，我们并不会直接使用形式化的定义，而是会使用

"这是模式串从 向左侧延伸的，和从 向左侧延伸的，两个子串的最长匹配。"

的方法计算。我们以后再谈实现。

---

综上所述，当 shift 为 时，我们在 失配， ，此时：

细心的读者可能已经发现，这样的算法的复杂度并不尽如人意：在匹配数量 很多的时候，这个算法的复杂度并不佳。可以证明，这个算法的复杂度为 。

该复杂度的证明并不平凡，首先在 这篇论文^[2] 中由 Kunth 等证明（没错，这就是 KMP 算法的论文），我们在这里大概说明思路：

我们考虑复杂度为 ：

1. 首先， 。（这并非紧界，Cole 的研究^[3]给出了 的结果）
2. 其次， 当 时，假设模式串第一次出现，结束在 位置，那么 ，通过归纳可以得到： 。

Galil 优化

之所以复杂度还有难看的 因子，是因为我们上面的优化都只优化了上面提到的优化方式的第一条：”减少需要考虑的 shift 数量。“其实，我们只需要一个 "trivial"（Galil, 1979）的，针对第二条”减少在考虑某个 shift 时，需要进行的比较。“的优化，匹配（不包括 的预处理）的时间复杂度就可以被优化到 。

我们称 是 的 周期(Period) ，当且仅当存在 满足 ，使得 是 的前缀。

我们称 是 周期的(Periodic) ，当且仅当它存在周期 。容易知道 ，其中 。

显然，非”周期的“模式串，因为它没有”重复性质“，其在目标串中的出现位置不会离的很近，因此也就目标串中出现很多次，具体来说是 。所以，对于非周期的模式串，匹配的复杂度降到了 。

对于“周期的”模式串 ，我们试图进行第二类优化。假设 的最小的周期为 ，满足 ，那么我们断言：在某个 shift 进行匹配的时候，除了“第一次”（上一次在某个 shift 的匹配没有匹配到模式串）需要匹配到完整的模式串，随后的紧接匹配都只需要从右往左匹配到一个长度为 的“周期”长度，即可断言这样的匹配必然是完整的。

感性理解：前面已知存在一个完整匹配，包含一堆周期，下面再找，就只需要把最后一个周期补全。

如果后面没有出现立即周期，那么模式串下一次出现会很远（大致是一个模式串的距离），因此出现次数一定不会很多。

这个优化的实现只需要在原始算法中增加一个变量 替换到循环的下界即可。周期的计算也是在预处理中可以解决的。我们可以证明，BM 算法经过这样的优化后，匹配的复杂度只有 。

该复杂度的证明不在本文讨论的范畴，可以去寻找 Galil 原始论文查看。基本方法和上述证明归纳过程相同。

---

匹配过程的伪代码大致如下：

j = 0, l = -1
while s <= n - m:
    i = m - 1
    while i != l and p[i] == t[s + i]:
      i = i - 1
    if i == l:
      print(match at j)
      l = m - k
      i = 0
    else:
      l = -1
    s = s + max(delta1(i, t[s + i]),
                delta2(i))

---

本文阐述了 BM 算法的基本优化（Bad Character 和 Good Suffix 优化），还介绍了 Galil 优化，最终将字符串匹配的复杂度降低到 。

但是，具体实现 BM 算法还是相当的困难，尤其是 的预处理，这会在第二部分介绍。

参考资料

[1]

Boyer 等人的论文: https://dl.acm.org/doi/10.1145/359842.359859

[2]

这篇论文中: https://epubs.siam.org/doi/10.1137/0206024

[3]

Cole 的研究: https://dl.acm.org/doi/10.5555/127787.127830