<p>Boyer-Moore 比 std::string::find 更快因其从模式末尾匹配并用 bad_char 表跳过无效位置，在长文本短模式下平均复杂度达 O(n/m)；手写最小实现只需 bad_char 规则，用 std::array 存最右位置，失配时按 std::max(1, j - bad_char[txt[i+j]]) 跳跃。</p>
为什么 Boyer-Moore 比 std::string::find 更快？
它不逐字符比对，而是从模式串末尾开始匹配，并利用两个预计算表（bad_char 和 good_suffix）大幅跳过不可能匹配的位置。在长文本 + 短模式（如日志关键词搜索、DNA 序列扫描）下，平均时间复杂度接近 O(n/m)，远优于朴素算法的 O(n×m)。
如何手写一个最小可用的 Boyer-Moore 实现（C++17）？
只实现 bad_char 规则即可覆盖绝大多数实用场景，且代码简洁、不易出错。完整版（含 good_suffix）逻辑复杂，边界条件多，实际性能提升有限，反而容易引入 off-by-one 错误。
关键点：
-
bad_char表用std::array<int></int>实现，初始化为 -1，记录每个字节在模式串中**最右出现位置** - 匹配时从模式末尾开始比较；失配时查表，计算跳跃步数：
std::max(1, j - bad_char[txt[i+j]]) - 注意：必须确保
i不越界，每次更新后检查i
#include <array>
#include <string>
#include <algorithm>
<p>int boyer_moore_search(const std::string& txt, const std::string& pat) {
if (pat.empty()) return 0;
if (pat.size() > txt.size()) return -1;</p><pre class='brush:php;toolbar:false;'>std::array<int, 256> bad_char;
bad_char.fill(-1);
for (size_t i = 0; i < pat.size(); ++i) {
bad_char[static_cast<unsigned char>(pat[i])] = static_cast<int>(i);
}
int i = 0;
const int n = static_cast<int>(txt.size());
const int m = static_cast<int>(pat.size());
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && pat[j] == txt[i + j]) --j;
if (j < 0) return i;
int shift = j - bad_char[static_cast<unsigned char>(txt[i + j])];
i += std::max(1, shift);
}
return -1;}
立即学习“C++免费学习笔记（深入）”；
哪些情况会让 Boyer-Moore 变慢甚至退化？
当模式串含大量重复字符（如 "aaaa"），或文本与模式高度相似（如搜索 "abababab" 在 "abababababab..." 中），bad_char 规则几乎无法跳过，退化为 O(n×m)。此时应切换策略：
- 对极短模式（
len < 4），直接用std::search或循环比较 - 对重复性强的模式，可提前检测字符分布熵，低于阈值时 fallback 到
std::string_view::find - 若需多模式匹配（如同时搜 100 个关键词），不要单个 Boyer-Moore 套循环，改用 Aho-Corasick
使用 std::boyer_moore_searcher 有什么坑？
C++17 引入了 std::boyer_moore_searcher，但它的实现质量严重依赖标准库厂商：
- libstdc++（GCC）：仅实现
bad_char，且内部用std::unordered_map建表，小模式下开销反超手写数组 - libc++（Clang）：同样未实现
good_suffix，且部分版本存在迭代器失效 bug - 所有实现都不支持自定义字符类型（如
char16_t），也不暴露跳转逻辑供调试
除非你明确测试过目标平台的性能且结果满意，否则建议优先手写轻量版——控制权在自己手里，一行 bad_char 表就能压住大部分场景。
真正难的不是写对算法，是判断什么时候不该用它。
