C++ string find方法的时间复杂度与Boyer-Moore对比
std::string::find() 的时间复杂度是多少？不同标准库实现的查找算法差异（如 libstdc++ vs libc++），何时应该使用更高效的搜索算法（Boyer-Moore/KMP）？
回答
Yahuda
std::string::find() 复杂度：
- 没有复杂度保证，但典型实现使用朴素匹配（两重循环，最坏 O(n*m)）。
- libstdc++：朴素搜索（逐个字符比较）。
- libc++：朴素搜索（但用 traits::eq 和 memcmp 优化）。
- 对于短模式和随机文本，朴素算法因简单内存访问模式通常快于亚线性算法。
更好的搜索算法：
| 算法 | 预计算 | 最坏情况 | 最好情况 | 适用场景 |
|---|---|---|---|---|
| 朴素 | 无 | O(n*m) | O(n) | 短模式/平均情况 |
| KMP | O(m) | O(n+m) | O(n) | 含重复子串的模式 |
| Boyer-Moore | O(m+Σ) | O(n*m) | O(n/m) | 长模式/大字母表 |
| Boyer-Moore-Horspool | O(m+Σ) | O(n*m) | O(n/m) | 简化的 BM，常用 |
何时替换 find()：
- 长文本中频繁查询固定模式。
- 模式较长（>10 字符）。
- 搜索大量文本（MB/GB 级）。
C++ 实现：
// C++17 std::boyer_moore_searcher (在 <functional> 中)
#include <functional>
string text = "...";
string pattern = "needle";
boyer_moore_searcher searcher(pattern.begin(), pattern.end());
auto it = searcher(text.begin(), text.end());
建议：日常使用 find() 足够，性能瓶颈时用 boyer_moore_searcher。