boyer-moore坏字符表须用unsigned char作下标，vector大小256初值-1；好后缀suffix[i]表示以i结尾的后缀匹配真后缀的最大长度，prefix[i]标记是否为border；位移取bad_shift与good_shift最大值且至少为1。
Boyer-Moore 的 bad_char_shift 表怎么建才不越界？
建表本质是为每个字符预存「若失配，模式串该右移多少位」，但 C++ 中 std::string::at() 或数组索引容易因字符值超出 0–255 范围而崩——尤其用 char 当数组下标时，负值会转成巨大正索引。必须统一用 unsigned char 做键。
实操建议：
- 用
std::vector<int></int>（大小 256）初始化全为-1，表示该字符在模式串中未出现 - 遍历模式串
pattern时，对每个位置j，执行bad_char[static_cast<unsigned char>(pattern[j])] = j</unsigned> - 查表时也必须
static_cast<unsigned char>(text[i])</unsigned>，否则 ASCII 扩展字符或 locale 相关字符会错位 - 别用
map<char int></char>——常数大、缓存不友好，BM 对性能敏感
好后缀规则的 suffix 和 prefix 数组怎么填？
这是最容易写反的地方：suffix[i] 表示「以 i 结尾的后缀」能与模式串某个真后缀匹配的最大长度，不是从开头匹配；而 prefix[i] 标记该后缀是否恰好匹配模式串开头（即是否为 border）。很多人误把 i 当作起始位置。
实操建议：
- 倒序构建：
i从len - 2到0（最后一个字符的后缀长度为 0，跳过） - 对每个
i，设len_suffix = 0，然后从末尾向前比对：只要pattern[j] == pattern[i + (len - 1 - j)]就累加len_suffix，直到失配 -
prefix[i]只需检查suffix[i] == len - i是否成立——即匹配长度刚好撑满从i到末尾的区间 - 别漏掉边界：当整个后缀匹配模式串前缀时（
i == 0），prefix[0]必须为true，否则后缀规则在首字符失配时无法触发最大位移
主循环里，坏字符和好后缀位移量怎么取 max？
Boyer-Moore 正确性依赖「取两者位移中的较大值」，但新手常写成 shift = std::max(bad_shift, good_shift) 后直接跳，却忘了：如果 good_shift 为 0（比如后缀完全不匹配且无 border），而 bad_shift 算出来是负数或 0，就会死循环。
实操建议：
-
bad_shift计算为i - bad_char[...]，若结果 ≤ 0，说明坏字符在模式串中位置 ≥ 当前比较点，此时按规则应至少右移 1 位——所以强制bad_shift = std::max(1, i - bad_char[...]) -
good_shift来自两个分支：若存在等长后缀（suffix[i] > 0），则位移为len - suffix[i]；否则找最长 border（prefix[j]为 true 的最小j > i），位移为len - j；都找不到就退化为len - 最终
shift = std::max(bad_shift, good_shift)，但必须确保shift >= 1，否则加一句shift = std::max(shift, 1)
为什么在短模式串（
预处理开销固定：坏字符表要扫一遍模式串，好后缀表要 O(m²) 构建（标准实现）或 O(m) 但代码复杂。当 m 很小时，这部分时间占比压倒主循环节省的比较次数。
实操建议：
- 实际工程中，通常设阈值（如
m ）直接切回 <code>std::string::find()或手写朴素匹配 - 不要盲目套用 BM——它真正优势在长模式串（> 15 字符）+ 高熵文本（如源码、日志），此时坏字符跳过大量位置
- 如果文本含大量重复字符（如 DNA 序列），好后缀规则收益下降，坏字符表又可能退化（多数字符相同），这时要考虑
Shift-And或AC 自动机
C++ 实现 BM 最容易被忽略的，其实是字符类型转换的一致性——一个 char 没 cast 成 unsigned char，整张坏字符表就全偏了；而好后缀表里 prefix 数组若没正确标记 i==0 的情况，会导致首次失配只挪 1 位，彻底失去 BM 的加速意义。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
