字符串匹配算法图解坏字符好后缀
BM_BC算法：以终为始
看完你能逐字符画出BM匹配过程，并说清为何从末尾倒着比更快
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
字符串匹配算法图解坏字符好后缀
BM_BC算法：以终为始
看完你能逐字符画出BM匹配过程，并说清为何从末尾倒着比更快
以终为始：从右往左比对
前一页说了BM的核心思路：坏在哪个字符不重要，重要的是错在哪。但错的位置怎么发现？如果你拿着一个词在书里找，眼睛往往会先扫它的结尾——BM也是这么干的。
对齐：左端对齐
模式串先与文本窗口左端对齐，位置记为 s
比对：从右往左
每次从模式串末位字符开始，向左逐一比对
为何先看末位
末位失配最常见，可立刻触发最大跳跃，越早发现错得越多
查字典找词对应 →从右往左比对
人找单词先扫结尾几个字母，对应先比对模式串末位
不对称性
上一页我们让比对从右往左走。现在模式串和文本在某位对不上了：坏字符和它左边的好后缀同时出现，先想谁？答案是坏字符，因为它更靠右，信息离终点更近。
失配两份信息
右端对不上的坏字符 + 左边已匹配的后缀，各能推动不同的跳转
以终为始
终点在右端，离终点越近的失配越先被利用
BC 独立思考
只看坏字符在模式串中的位置，规则简单、可预算成表
GS 留给后手
好后缀信息更强但更复杂，BC 先粗跳、GS 再精修
查户口先看户口本封面对应 →失配先看坏字符
封面（最右坏字符）一眼定去向，内部细节（好后缀）再细查
善待教训
从右往左比对失配后，前面比对成功的那段「好后缀」其实花了成本。这段已匹配信息里藏着位置线索——失配不是白发生的，教训必须被记账利用。
失配即信息
失败排除了哪些对齐位置，下次直接跳过
坏字符记录
预处理每个字符最后出现位置，失配时查表滑移
教训入账
模式串预处理建表，把可能教训提前算好
错题本对应 →BC表
错题本记下易错点供下次跳过，BC表记录字符位置供失配时查
前轻后重
上一页我们看到 BM 从右往左比对，错位信息来得不一样。既然越靠右的字符越早被检验，那么一次失配带来的跳转价值，也天然取决于失配发生在模式串的哪个位置。
后段先受检
从右往左比对，模式串后段字符最先接触文本
后段教训更值钱
失配越靠右，可安全右移的幅度往往越大
前段只做兜底
靠前的失配可用位移小，退化时也不至于负移
设计取向
预处理的坏字符表按最后一次出现位置记录
改试卷从最后一题开始对应 →前轻后重
越先批改（越靠后）的题暴露的问题，越能决定重考的范围
自测：BC 策略辨析
点击作答
BM 算法从右往左比对时遇到坏字符失配，坏字符策略决定模式串如何滑动，其移动依据是什么？
小结与延伸
- ✓BC表在匹配前就能建好，一次预处理全程复用
- ✓从右往左比对，坏字符暴露得越早，跳得越远
- ✓位移只由坏字符在模式串中最右位置决定
- ✓教训全部兑现，绝不回头重比已对齐的文本
- ✓BC只看单个字符；失配发生在尾部时它近乎失效
延伸主题：GS好后缀策略：失配信息更充分BC与GS取最大位移合成完整BM坏字符表扩展：多字节与字符集边界
课后思考
先自己想几分钟，再对照参考答案，看看思路是否一致。
1BM 算法为什么敢于从右往左比对，甚至整段跳过文本？它的底气来自哪里？
参考答案回顾核心：底气来自好后缀与坏字符两张表——它们由模式串自身预处理得出，保证任何跳过都不会漏掉匹配。跳过的每一格都已被证明不可能匹配成功。
2如果把它用到中文文本搜索（字符是宽字符而非字节），预处理表会遇到什么新问题？
参考答案应用层面：表按字符取值建立，宽字符取值范围大，坏字符表可能变得稀疏、耗内存。可改成哈希或按低几位分桶，这是工程实现里真实的取舍。
3模式串越短，BC 策略的跳跃优势会不会反而消失？边界在哪里？
参考答案边界思考：模式越短，一次比对覆盖的信息越少，跳跃幅度上限受模式长度约束；极短模式下与朴素算法差距缩小。模式很长时跳跃优势才充分体现。