第二十五讲：字符串匹配算法进阶——Rabin-Karp、Boyer-Moore、Sunday与AC自动机
字符串匹配，说白了就是「在一堆字符里找一段特定的字符」。你写个 strstr() 就搞定了？嗯，那是数据量小的时候。一旦文本上百万字符，模式串几十上百，暴力法的 O(mn) 就扛不住了。
我早年做嵌入式协议解析时，就吃过这个亏。一个日志文件几兆，用暴力匹配去搜关键字，设备直接卡死。后来换了 Rabin-Karp，速度翻了几倍。今天我把这几个进阶算法掰开揉碎了讲给你听。
核心知识点一览：
- Rabin-Karp：用哈希做滑动窗口，适合多模式匹配场景
- Boyer-Moore：从右往左匹配，坏字符+好后缀跳得飞快
- Sunday：BM的简化版，只看下一个字符，实现简单
- AC自动机：Trie + fail指针，一次遍历匹配所有模式串
一、Rabin-Karp：用哈希做快速筛选
Rabin-Karp 的思路很直接——把模式串算出一个哈希值，然后在文本上滑动窗口，每滑一次算一下子串的哈希。如果哈希相等，再逐字符确认。
你想想看，暴力匹配每次都要比较 m 个字符，而 Rabin-Karp 只比较哈希值（O(1)），只有哈希冲突时才去逐字符确认。这就像先筛一遍，再细查。
我的经验：我在做入侵检测系统时，需要同时匹配几十个恶意特征串。用 Rabin-Karp 配合滚动哈希，一次扫描就能筛出所有候选位置，比暴力匹配快了不止一个数量级。
滚动哈希是关键。比如用 base=256，模一个大质数。计算下一个窗口的哈希时，不用重新算，而是：
// 滚动哈希核心公式
hash = (hash - text[i] * pow_base[m-1]) * base + text[i+m];
hash %= MOD;嗯，这里要注意：模数选不好容易哈希碰撞。我建议选 10^9+7 或 10^9+9，冲突概率极低。
二、Boyer-Moore：从右往左，跳着走
Boyer-Moore 是我个人最喜欢的单模式匹配算法。它不走寻常路——从模式串的最右边开始匹配。
为什么从右往左？因为一旦某个字符不匹配，你可以根据这个「坏字符」在模式串中的位置，直接跳一大段。比如模式串是 "abc"，文本是 "xbc..."，从右往左比，第一个字符 'c' 和 'x' 不匹配，而 'x' 根本不在模式串里——直接跳 3 位！
坏字符规则：不匹配时，看文本中的这个字符在模式串中最后一次出现的位置，把模式串移过去对齐。
好后缀规则：已经匹配的后缀部分，如果在模式串前面还有相同的子串，就移过去对齐。
实际实现时，取坏字符和好后缀两者中跳得远的那个。我在一个文本搜索工具里用过 BM，处理 10MB 的日志文件，平均只需要比较不到 20% 的字符。
我曾经踩过的坑：BM 的预处理表如果实现不对，跳转距离算成负数，直接死循环。建议先实现坏字符表，测试通过后再加好后缀。别一口气全写完再调试，那会非常痛苦。
三、Sunday：BM 的「极简版」
Sunday 算法是 BM 的简化。它只看匹配失败时，文本中模式串末尾的下一个字符。说白了，就是「下一个字符在不在模式串里？不在就跳 m+1 位，在就对齐到那个位置」。
为什么这样也行？因为如果下一个字符都不在模式串里，那模式串无论如何都不可能包含它，直接跳过整个模式串加一个字符，绝对安全。
// Sunday 跳转表构建
int shift[256]; // 所有字符初始化为 m+1
for (int i = 0; i < m; i++) {
shift[pattern[i]] = m - i; // 字符距末尾的距离
}
// 匹配过程
int i = 0;
while (i <= n - m) {
int j = 0;
while (j < m && text[i+j] == pattern[j]) j++;
if (j == m) return i; // 匹配成功
// 看下一个字符
i += shift[text[i + m]];
}你看，代码比 BM 短了一大截。Sunday 在英文字符集上表现很好，因为字母表大，跳转机会多。但如果是中文字符或小字符集，效果会打折扣。
四、AC自动机：一次遍历，匹配所有
前面三个都是单模式匹配。如果你有几十上百个模式串要同时匹配呢？比如敏感词过滤、病毒特征检测。这时候 AC 自动机就登场了。
AC 自动机 = Trie 树 + fail 指针。Trie 树把所有的模式串建成一棵树，fail 指针则是在匹配失败时告诉你「下一步该跳到哪」。这样你只需要遍历一遍文本，就能找出所有出现的模式串。
构建步骤：
- 把所有模式串插入 Trie 树
- BFS 构建 fail 指针：根节点的孩子 fail 指向根，其他节点的 fail 指向父节点 fail 的对应孩子
- 匹配时，每读一个字符，沿着 Trie 走，如果走不通就跳 fail，边走边检查是否有模式串结束标记
我记得有一次做协议解析，需要同时匹配 200 多个关键字。用 AC 自动机，一次扫描就全搞定，时间复杂度 O(n + 总模式串长度)。如果用暴力匹配，每个关键字都要扫一遍，那就是 O(200 * n)，差距巨大。
我的建议：AC 自动机的 fail 指针构建是核心，也是最容易写错的地方。建议先画一棵小 Trie 树，手动推导每个节点的 fail 指针，再对照代码实现。我当年就是这么干的，一次通过。
五、算法对比与选型
| 算法 | 预处理时间 | 匹配时间 | 适用场景 |
|---|---|---|---|
| 暴力匹配 | 无 | O(mn) | 小数据量，临时用 |
| Rabin-Karp | O(m) | O(n) 平均 | 多模式串、长文本 |
| Boyer-Moore | O(m + σ) | O(n/m) 最佳 | 单模式、大字符集 |
| Sunday | O(m + σ) | O(n/m) 平均 | 实现简单，英文字符 |
| AC自动机 | O(总模式串长) | O(n) | 多模式串匹配 |
选型其实不难：单模式匹配，字符集大（比如英文）用 BM 或 Sunday；字符集小（比如 DNA 序列）用 Rabin-Karp；多模式匹配直接上 AC 自动机，别犹豫。
好了，这一讲的内容就到这。字符串匹配是嵌入式开发、协议解析、文本处理中的基本功。你把这些算法吃透了，以后遇到性能瓶颈，心里就有底了。