Boyer–Moore · bad character rule

Boyer–Moore：从右往左比，大步跳过

KMP 让文本指针不回退，但还是逐字符往前挪。Boyer–Moore 更激进：它在每个窗口里从右端向左比较，而且一旦失配，不满足于挪一格，而是问「在不漏掉任何匹配的前提下，窗口最远能安全跳到哪」——据此一次跳过大段从未细看的 text。text 越长、字母表越大，跳跃越大。

1 · 失配后的安全右移量：两条规则各给一个答案

「能安全跳多远」由两条互补的规则各算一个答案，失配时取较大者。

bad character 规则盯着让本次失配的那个 text 字符：它在 pattern 里出现在哪。
good suffix 规则盯着失配前已经匹配上的那截 pattern 后缀：它在 pattern 里还能怎么重新对上。

每条规则背后都是一张只依赖 pattern、可一次性预处理的表。§2 与 §3 分别拆开这两张表，§4 再把它们合并。

2 · 规则一：bad character 表

last[c] = 字符 c 在 pattern 中最后一次出现的下标（没出现则视为 −1）。失配发生在 pattern 的第 j 位、bad character 是 text 里的 c 时，窗口右移 $\max (1, j - last[c])$ ：把 pattern 里最后那个 c 对齐到失配处；若 c 根本不在 pattern 里，整段窗口都可以跳过去。

这张表的算法很短：只要把 pattern 从左到右扫一遍，对每个字符执行 last[pattern[k]] = k——后扫到的覆盖先扫到的，留下的自然就是「最后一次出现」。代价是 $O(m + |\Sigma|)$ ，其中 $|\Sigma|$ 为字母表大小，而且只看 pattern、与 text 无关。以本页 pattern GCAGAGAG（下标 0–7:G C A G A G A G）为例：字符 G 最后现于 7、C 现于 1、A 现于 6，即图 2-1 里那张表。取最后一次出现的原因是：右移时，要让 pattern 里尽量靠右的那个 c 对齐到失配的 text 字符；选更靠右的 c，窗口移动最少、不会越过任何候选位置——若选更靠左的同字符，窗口会跨过去，可能漏掉夹在中间的匹配。

图 2-1 · bad character 表的构建与每次失配的跳跃距离，读数同时给出 Boyer–Moore 与同输入下 naive matching 的比较次数。可改 pattern 观察表如何变化。

在字母表较大、pattern 较长时，Boyer–Moore 往往只看 text 里一小部分字符就能排除大量位置，是少数平均比 text 长度还快（亚线性）的查找算法。

3 · 规则二：good suffix 表

失配那一刻，pattern 的右段已经有一截和 text 对上了——把这截已匹配的后缀叫 good suffix，记作 t。既然 t 刚刚对上过，右移之后我们当然希望它还能继续对上，而不是盲目挪一格。good suffix 表就是为「每一种 t（即每个失配位置）」预先算好「该往右挪多少」。取移动量分两种情况：

3.1 · Case 1 · pattern 内部的另一处出现

那就把别处那一份 t 滑过来、对齐到刚匹配的位置。还有个附加条件（strong good suffix）：那一份 t 左边的字符必须不等于当前 t 左边的字符——否则滑过去会立刻以同样的字符再次失配，移动无效。

图 3-1 · Case 1：pattern 内部别处整段出现过 t 时把那一份滑过来对齐。可观察 strong good suffix 的附加条件何时把候选排除掉。

3.2 · Case 2 · t 的后缀与 pattern 前缀的重叠

这时整段对不上了，退而求其次：让「既是 t 后缀、又是 pattern 前缀」的那一小段重新对齐到 text 末端。取最长的这种段，挪得最少。

图 3-2 · Case 2：整段 t 不再出现时，让既是 t 后缀又是 pattern 前缀的那一小段重新对齐到 text 末端。

（两种情况都不满足时，说明这截 t 在 pattern 里再无可用的重现 → 直接右移整个 $m$ 。）

3.3 · good suffix 表的计算方式

注意 good suffix 只跟 pattern 有关、与 text 无关，和 KMP 的 prefix function 一样，本质是 pattern 的自我分析。标准做法对 pattern 的各个后缀做一遍类似 border（最长相等前后缀）的预处理，用两趟扫描填出 shift 数组：一趟覆盖 Case 1（记下每段 t 在 pattern 内最近的另一处出现），一趟顺着 border 链补上 Case 2（后缀 = 前缀）。整体 $O(m)$ ，和 bad character 表一样属于一次性预处理。

4 · 两条规则的合并

失配时的窗口右移量，就是两条规则各算一个、取较大者（并至少移 1 格）：shift = max(badCharShift, goodSuffixShift)。它们正好互补：bad character 在字母表大时单次右移量往往很大，却可能被 pattern 的高度自相似（像 GCAGAGAG）拖成很小的跳，good suffix 恰好补足这种情形。

两张表都只依赖 pattern、属于一次性预处理，建好后扫描 text 时每次失配只是查表、跳跃。图 2-1 只用 bad character，单独已能展示大步跳过的直觉；图 4-1 跑完整的 Boyer–Moore，每次失配同时算出两条规则的右移量并取较大者。

图 4-1 · 完整 Boyer–Moore 的逐窗口执行，每次失配并列显示两条规则各自的右移量与最终采用值。可用 GCAGAGAG 观察 good suffix 在 bad character 偏小时如何顶上来。

GCAGAGAG 高度自相似，bad character 常常只能给出很小的右移，因为失配字符在 pattern 里到处都是；这时 good suffix 给出更大的安全跳跃。若换成字母表更大、重复更少的 pattern，主导权就反过来落到 bad character 手上。

5 · 最坏情况并不线性

一个常见的误解是「加上 good suffix 就把最坏情况压到线性了」。实际不然：当 pattern 真的在 text 里出现时，原始 Boyer–Moore 的最坏情况仍是 $\Theta(nm)$ [1]。

本页引擎上实测即可看到。text 取 $a^{80}$ 、pattern 取 aaa 时，Boyer–Moore 用了 234 次字符比较，而 naive matching 同样是 234 次，两者一次都没差。 $n$ 取 10、20、40、80 时 BM 的比较次数分别是 24、54、114、234。原因是每个窗口都要把整个 pattern 比完才命中，两条规则都给不出大于 1 的跳。

反过来，pattern 不出现时 BM 确实很快：同样的 $a^{80}$ 找 bbb 只要 26 次比较，每字符 0.33 次，亚线性。

要在有匹配时也保持线性，需要额外的 Galil 规则：记住上一次匹配已经确认过的那段，下一窗口跳过重复比较。Apostolico–Giancarlo 变体则给出更直接的 $2n$ 比较上界 [2]。这两者本页的引擎都没有实现。

6 · 参考文献

Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences，第 2 章（原始 Boyer–Moore 在 pattern 出现时为 $\Theta(nm)$ ，以及 Galil 的修正）. Cambridge University Press.
Cole, R. (1994). Tight bounds on the complexity of the Boyer–Moore string matching algorithm. SIAM Journal on Computing, 23(5), 1075–1091.