坏字符规则的核心判断逻辑是：当模式串从右向左匹配失败时，依据失配位置的“坏字符”在模式串中最右出现的位置决定滑动距离；若该字符未出现，则模式串整体右移跳过该位置，滑动距离为当前偏移量减去最右索引（未出现时为−1），该索引须预处理存储以避免退化为暴力匹配。
坏字符规则的核心判断逻辑是什么
坏字符规则本质是：当模式串 pattern 从右往左匹配失败时，看文本中那个“坏字符”（即失配位置的文本字符）在 pattern 中**最靠右的出现位置**；如果它根本没出现过，就直接把 pattern 整体滑过这个位置。
关键不是“有没有”，而是“最右在哪”——这决定了你能滑多远。滑动距离 = 当前对齐位置偏移量 − 坏字符在 pattern 中最右索引（若未出现则为 −1）。
实际编码中，这个“最右索引”必须预处理好，不能每次现场扫描，否则退化成暴力算法。
怎么预计算坏字符表（以 ASCII 字符为例）
用一个大小为 256 的数组 badChar，初始化为 −1；遍历 pattern 时，对每个字符 c，直接赋值 badChar[c] = i（i 是其下标）。因为是顺序遍历，后出现的相同字符会自然覆盖前面的，结果就是最右位置。
std::vector<int> buildBadCharTable(const std::string& pattern) {
std::vector<int> badChar(256, -1);
for (int i = 0; i < pattern.size(); ++i) {
badChar[static_cast<unsigned char>(pattern[i])] = i;
}
return badChar;
}
注意点：
- 必须用
unsigned char强转，否则负值字符（如某些平台的char默认 signed）会导致数组越界 - 表大小不一定要 256——如果只处理 ASCII，256 安全；若支持 Unicode，得换哈希表或其它结构，但此时坏字符规则本身效率已大幅下降
- 空模式串或单字符模式不需要此表，但代码里仍建议统一构建，避免分支逻辑
匹配过程中如何用坏字符表决定滑动步长
假设当前对齐位置是文本索引 txtIdx，模式串从右端开始比对，在位置 j（相对于 pattern 起始索引，0-based）失配，对应文本字符是 txt[txtIdx + j]。
滑动偏移量 = j − badChar[txt[txtIdx + j]]
但必须保证至少滑 1 步，所以最终步长是 std::max(1, j − badChar[...])。
常见错误：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 误用
j为从左往右的索引（比如j = 0表示最左），而坏字符规则依赖从右往左的失配位置 - 没做
std::max(1, ...)，导致算出 0 步甚至负步，陷入死循环 - 把
txtIdx和j混淆：滑动影响的是txtIdx，不是j
坏字符规则单独用够吗？什么时候必须结合好后缀规则
单独用坏字符规则能工作，但最坏时间复杂度仍是 O(n × m)（比如文本全是 'A'，模式是 "AAA...AB"），因为每次只滑 1 步。
好后缀规则能保证每次至少滑 1 位、且在多数情况下滑得更远。生产环境的 Boyer-Moore 实现**必须同时维护两个表**，每轮取两者滑动距离的最大值。
容易被忽略的一点：
立即学习“C++免费学习笔记（深入）”；
坏字符表只依赖 pattern 内容，可以一次构建复用；但好后缀表构建逻辑复杂，且和 pattern 长度强相关——如果你只搜一次短模式，其实用 KMP 或内置 std::search 更省事；真要手写 Boyer-Moore，大概率是在反复搜索同一模式、且模式较长（≥ 10 字符）、文本极大时才值得投入预处理成本。
