坏字符规则是bm算法提速核心，指从右向左匹配时首个失配字符（来自主串），位移量=坏字符在模式串中最右位置索引的差值（未出现则为-1），须取最右位置以防漏匹配，预处理坏字符表支持o(1)查询。
bm算法的位移加速，核心不在“多比几个字符”，而在于“少比很多字符”——坏字符规则正是实现这一点的关键机制。它不靠逐位试探，而是根据一次失配，直接算出模式串该跳多远，跳得越准、越远，总比较次数就越少。
坏字符是怎么定义的
坏字符不是主串或模式串“本身不好”，而是当前比较轮次中第一个不匹配的字符。BM算法从右往左比，所以这个“第一个”出现在右侧靠后位置。比如模式串是 "ABAC"，主串某段是 "ABAD"，从末尾开始比：C vs D → 不匹配 → D 就是坏字符。
注意：坏字符一定来自主串，且只取本轮失配位置上的那一个字符；它在模式串中可能有、可能没有、也可能有多个。
位移量怎么算：关键看“最右出现位置”
位移不是凭经验估的，而是严格按公式：
位移 = 当前坏字符在主串中的位置索引 － 该字符在模式串中最右出现的索引
更实用的写法（以模式串下标从0开始）：
若坏字符 c 在模式串中最后一次出现在位置 last[c]（未出现则为 -1），当前失配发生在模式串第 j 位（从右数，j 从0开始计，即末位是 j=0），则向右滑动：
shift = j − last[c]
- 例如模式串 "ABAC"，构建坏字符表得：A→2，B→1，C→3，D→-1
- 若坏字符是 D，j=0 → shift = 0 − (−1) = 1 → 实际应跳过整个模式串长度（4），但此公式需结合起始对齐理解；更稳妥做法是统一用“主串失配位置 − 模式串最右c位置”
- 若坏字符是 A，且 j=2（即从右数第3位失配），last[A]=2 → shift = 2−2 = 0？这显然不合理 —— 所以实际实现中，j 应取其在模式串中的绝对下标（如末位是 m−1），公式为：shift = (m−1) − last[c]，再与好后缀位移取较大值
为什么必须取“最右出现位置”
因为只有对齐最右侧的那个相同字符，才能保证不漏掉潜在匹配。如果取左边的A，模式串会滑得太远，跳过本该重叠的正确对齐点。
举个典型反例：
模式串："BABAC"（长度5）
主串片段："XBABAC"
若失配时坏字符是 C，它在模式串中出现在位置 4（最右）和 2。若错误取位置 2 对齐，模式串会左移或滑动不足，导致错过末尾的完整匹配。
所以预处理时，遍历模式串只需从左到右扫一遍，不断覆盖同字符的位置值，自然留下最右索引。
坏字符表怎么建才高效
建表目标就一个：O(1)查出任意字符 c 的 last[c]。两种主流方式：
- 定长数组法（适合ASCII等小字符集）：开大小为256的整型数组，初值全填 -1；遍历模式串每个字符 pattern[i]，执行 bc[ord(pattern[i])] = i
- 哈希字典法（适合Unicode或稀疏字符）：用 dict 或 map，键为字符，值为最右索引；同样遍历一次，遇到就更新
注意：不要在每次匹配时重建表；固定模式串务必缓存复用。表建错或没缓存，提速效果直接打五折。
