KMP算法稳定可靠，适合长模式串；Boyer-Moore实际最快，利用坏字符和好后缀跳过无效比较；Rabin-Karp基于哈希，便于多模式匹配；暴力法简单但效率低。
在C++中实现高效的字符串查找，关键在于选择合适的匹配算法。不同场景下，算法的性能差异明显。暴力匹配虽然简单，但在长文本中效率低下。而KMP、Boyer-Moore和Rabin-Karp等算法通过预处理或跳转策略显著提升效率。
暴力匹配（Brute Force）
最直观的方法是逐个比较主串和模式串的字符。
- 时间复杂度：O(n×m)，最坏情况下每个位置都要比较整个模式串
- 空间复杂度：O(1)
- 适合短模式串或小规模数据
实现简单，无需额外存储，但面对重复字符多的文本时效率差。
KMP算法（Knuth-Morris-Pratt）
利用已匹配部分的信息，避免回溯主串指针。
立即学习“C++免费学习笔记（深入）”；
- 核心是构建“部分匹配表”（next数组），记录模式串前缀与后缀的最长公共长度
- 时间复杂度：O(n+m)，预处理+匹配线性时间
- 空间复杂度：O(m)，存储next数组
适合模式串较长且存在重复子结构的情况。例如搜索"ABABC"时，当失配发生，可跳过已知重复前缀。
Boyer-Moore算法
从模式串末尾开始匹配，结合坏字符和好后缀规则大幅跳过无效位置。
- 坏字符规则：遇到不匹配字符时，将模式串向右滑动至对齐最近的该字符
- 好后缀规则：利用已匹配的后缀信息决定滑动距离
- 平均时间复杂度：O(n/m)，最坏O(n×m)
- 实际表现优异，尤其在英文文本中
常用于编辑器搜索功能。当模式串越长，跳过的字符越多，效率越高。
Rabin-Karp算法
基于哈希值比较，将模式串和主串子串转换为数值进行快速筛选。
- 使用滚动哈希（如多项式哈希）快速更新子串哈希值
- 时间复杂度：平均O(n+m)，最坏O(n×m)（哈希冲突多时）
- 适合多模式匹配或文件指纹检测
例如计算"abc"的哈希后，滑动到"bcd"只需减去a的贡献加上d的贡献。
基本上就这些。KMP稳定可靠，Boyer-Moore在实践中最快，Rabin-Karp便于扩展，暴力法适合简单场景。根据数据特点选择才是关键。
