BM 算法的好后缀策略
看完你能亲手推导好后缀移位表并解释每种失配情形
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
BM 算法的好后缀策略
看完你能亲手推导好后缀移位表并解释每种失配情形
什么是「好后缀」
上一页说，BM 算法遇到不匹配时不是一格一格退，而是聪明地跳。可跳之前得先看清现场：模式串尾部总有一段和文本对上了，这段「已拼好」的部分就是突破口——它叫好后缀。
已拼好的那几块对应已匹配的后缀；拼不下去时，找别处能接上相同形状的位置
好后缀引发的失配场景
从右向左比对时一旦失配，已匹配的尾部就是好后缀，下方分支展示三种滑动决策路径。
情形一：好后缀完整再现
当最长好后缀在模式串别处完整出现时，滑动到那个出现处对齐即可。
情形二：部分前缀匹配
好后缀在模式串里找不到完整再现时，退一步看它的子串是否匹配模式串前缀。
情形三：干脆滑过去
三种情形都不满足时，只能把整个好后缀滑过去，找新的对齐起点。
三种情形取最长
三种情形各有移动表，失配时到底听谁的？这是好后缀策略最易混淆的一步。
- 情形一：整个好后缀再次完整出现，滑到它对齐
- 情形二：只有前缀匹配，滑到前缀对齐
- 情形三：哪儿都不出现，直接滑过整个模式串
- 三表同时可查，每步都要三选一
- 三个候选距离各算出来
- 取最大者移动，绝不可能滑过头
实例体验：一步步滑动
以模式串 ABCAB 为例，完整走一遍好后缀驱动的滑动过程。
坏字符 vs 好后缀
两者都是 BM 的滑动依据，初学者常分不清失配时该看谁、听谁的。其实失配处右侧是好后缀、失配处本身是坏字符。
- 看失配处的文本字符
- 模式右移对齐该字符
- 无此字符可整段滑过
- 看失配处右侧已匹配段
- 右移找好后缀再次出现
- 找不到就退而求前缀
gs 表的构造思路
看看好后缀滑动表怎么预处理：从右往左匹配前后缀，三情形一次算完。
gs 数组先把情形二的前缀匹配位移算好，剩下没赋值的位置统一填 m，即情形三「干脆滑过去」。
自测：滑多远
BM 好后缀失配后，文本串指针该如何移动？
要点收束
- ✓好后缀是失配处右侧已匹配的子串
- ✓滑动距离取决于好后缀在别处的再现
- ✓三种情形取最长滑距，绝不回退
- ✓gs 表预计算，查询 O(1)
- ✓与坏字符策略取更大者，整体 O(n/m)
课后思考
先合上笔记自己想，再对照参考答案，看看思路差在哪。
参考答案取最短是为了不跳过任何可能的匹配位置。三种情形给出的是不同可信度的对齐点，取最远可能越过某个恰好匹配的起点，导致漏解，正确性就没了。
参考答案短模式下好后缀往往退化：m 小，子串在模式里再现的概率低，多数落在情形三。坏字符不受模式长度影响，短模式时通常靠坏字符拉动更多，这正是实践中两者结合的原因。
参考答案凡是「失败后利用已确认信息定位下一步」的场景都类似：比如 KMP 的失败函数本质也是利用已匹配前缀；编辑去重、日志压缩里利用重复片段跳过比对，都是同一思路的迁移。