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

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

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

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

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

每条规则背后都是一张只依赖 pattern、可一次性预处理的表。下面先分别看这两张表怎么来、怎么用，最后再合并。

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 + 字母表大小），而且只看 pattern、与 text 无关。以本页 pattern GCAGAGAG（下标 0–7:G C A G A G A G）为例：G 最后现于 7、C 现于 1、A 现于 6——这正是下面演示里那张表。取「最后一次出现」的原因：右移时，要让 pattern 里尽量靠右的那个 c 对齐到失配的 text 字符；选更靠右的 c，窗口移动最少、不会越过任何候选位置——若选更靠左的同字符，窗口会跨过去，可能漏掉夹在中间的匹配。

3 · 规则二：good suffix 表

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

3.1 · Case 1:pattern 内部别处也整段出现过 t

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

3.2 · Case 2：整段 t 没再出现，但 t 的某个后缀又是 pattern 的前缀

这时整段对不上了，退而求其次：让「既是 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 · 合并：shift = max(bad character, good suffix)

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

两张表都只依赖 pattern、属于一次性预处理；建好后扫描 text 时，每次失配就只是查表、跳跃。上面规则一的演示只用 bad character（单独已能展示「大步跳过」的直觉）；下面这个演示跑完整的 Boyer-Moore——每次失配同时算出两条规则的右移量、取较大者，你能看到 good suffix 在 bad character 偏小时顶上来。