Boyer-Moore 字符串匹配
字符串 · 坏字符规则
从右往左比，失配就大步跳
Boyer-Moore 是实践中最快的通用串匹配之一（编辑器查找、grep 的默认多半是它的变体）。它反直觉的地方有两点：把模式对齐到文本后，从模式的末尾开始、从右往左比；一旦失配，就用坏字符规则把模式大步右移——常常一次跳过好几个位置，甚至跳过整段。
坏字符规则
预处理出坏字符表：每个字符在模式中最右出现的位置（不在模式里记 -1）。P=abc → {a:0, b:1, c:2}。从右往左比时，若在 P[j] 处失配，看看是哪个文本字符（坏字符）没对上：
把模式右移，让坏字符对齐到它在模式里的最右出现处——右移量 = j − last[坏字符]。如果坏字符根本不在模式里，那这一整段对齐都没戏，直接把模式移过它（相当于跳过整段）。这就是 Boyer-Moore 能「跳着走」、平均亚线性的原因。
下面是 T=abcabxabc、P=abc（坏字符表 {a:0,b:1,c:2}）。点「下一步」逐步看：浅蓝色是当前对齐窗口，比较从右往左，已匹配的后缀标绿。留意两种跳：坏字符 a（在模式里）小跳，坏字符 x（不在模式里）大跳、跳过整段；最终命中于下标 0、6。右侧代码随每一步同步高亮。
T
a
b
c
a
b
x
a
b
c
P
a
b
c
模式对齐到文本开头；Boyer-Moore 从模式末尾（右端）开始，从右往左比
1function boyerMoore(text: string, pat: string): number[] {
2 const n = text.length, m = pat.length;
3 const last: Record<string, number> = {};
4 for (let i = 0; i < m; i++) last[pat[i]] = i; // 坏字符表
5 const res: number[] = [];
6 let s = 0;
7 while (s <= n - m) {
8 let j = m - 1;
9 while (j >= 0 && pat[j] === text[s + j]) j--; // 从右往左比
10 if (j < 0) {
11 res.push(s); // 全匹配 → 命中
12 s += 1;
13 } else {
14 const bc = text[s + j]; // 坏字符
15 s += Math.max(1, j - (last[bc] ?? -1)); // 大步右移
16 }
17 }
18 return res;
19}
文本 Tabcabxabc
模式 Pabc
坏字符表a:0 b:1 c:2
对齐 s0
j（从右往左）2
已找到—
1 / 12
还有「好后缀规则」
完整的 Boyer-Moore 有两条规则，每次失配取两者给出的较大右移量：
坏字符规则（本页）：让失配的文本字符对齐模式里它的最右出现处。
好后缀规则：已经匹配的那段后缀若在模式别处再次出现，就对齐过去（类似 KMP 的部分匹配表，但针对后缀）。
只用坏字符规则已经很快；两条合用能保证最坏也不退化。
坏字符规则（本页）：让失配的文本字符对齐模式里它的最右出现处。
好后缀规则：已经匹配的那段后缀若在模式别处再次出现，就对齐过去（类似 KMP 的部分匹配表，但针对后缀）。
只用坏字符规则已经很快；两条合用能保证最坏也不退化。
至此字符串匹配「三巨头」齐了：KMP（模式结构 / 部分匹配表）、Rabin-Karp（滚动哈希）、Boyer-Moore（从右往左 + 坏字符跳）——三条不同的加速路，各有所长。