串与模式匹配

环境：Windows 11 x64，GCC 13.1.0，分别用 -O0 与 -O2 编译。所有耗时与对拍结果都是本机实测。

一、先把 C 字符串的账算清

上一节说过 strlen 是 O(n)。把它放进循环条件是经典错误，但错误程度取决于编译器能看到多少：

for (size_t i = 0; i < strlen(s); i++) if (s[i] == 'a') n++;   /* 每轮重算长度 */

5 万字符的字符串，同一份代码两种优化级别：

-O0：每轮 strlen 202.6 ms | 提前算好 0.107 ms   → 差 1894 倍
-O2：每轮 strlen   1.3 ms | 提前算好 0.143 ms   → 差   9 倍

-O2 下 GCC 证明了循环体不会修改 s，把 strlen 提升出去了（所以只剩 9 倍，而且那 9 倍是循环本身没被向量化）。-O0 下的 1894 倍才是真正的 O(n²)。

两个结论：

复杂度分析要对编译后的代码做，不是对源码做。测性能必须固定优化级别，否则同一句代码差三个数量级。
但别依赖编译器替你兜底：只要函数签名从 const char * 变成 char *、或循环里有任何可能写入内存的调用，提升就失效。写法本身就要是对的。

二、KMP：`next` 数组的含义与推导

next[i] = 子串 p[0..i] 里最长的”真前缀 == 真后缀”的长度（真=不等于自身）。失配时模式串不用回退文本指针，只把模式指针跳到 next[k-1]。

std::vector<int> kmp_next(const std::string &p) {
    std::vector<int> nxt(p.size(), 0);
    for (size_t i = 1, k = 0; i < p.size(); i++) {
        while (k && p[i] != p[k]) k = nxt[k - 1];    /* 逐级退到更短的公共前后缀 */
        if (p[i] == p[k]) k++;
        nxt[i] = (int)k;
    }
    return nxt;
}

本机实测：

"abab"    → next = [0,0,1,2]
"aabaaab" → next = [0,1,0,1,2,2,3]
"aaaa"    → next = [0,1,2,3]

手工验一遍 "abab"：i=2（子串 "aba"）最长公共真前后缀是 "a" → 1 ✓；i=3（"abab"）是 "ab" → 2 ✓。"aaaa" 一路 0,1,2,3，是退化最严重的模式。

查找部分同样两处易错：

if (s[i] == p[k]) k++;
if (k == p.size()) { hits.push_back(i - k + 1); k = nxt[k - 1]; }   /* ← 必须回退，才能找重叠匹配 */

不写 k = nxt[k-1] 就只能找到不重叠的第一处，找 "aa" 在 "aaaa" 里有几处时会少算。

三、正确性靠对拍，不靠推理

KMP/Rabin-Karp 这类实现，边界一多肉眼根本查不完。我的做法是写一个必然正确的暴力版，用随机数据比对：

for (int t = 0; t < 2000; t++) {
    /* 字符表只取 3 种、长度 ≤ 200/12 —— 故意制造大量部分匹配与重叠 */
    auto a = brute_find(s, p), b = kmp_find(s, p), c = rk_find(s, p);
    assert(a == b && a == c);
}

2000 组随机用例（字符表只有 3 种，故意制造退化和重叠）全部一致=1

小字母表 + 短字符串是关键：字母表越小，“部分匹配后失配”的情况越多，越容易暴露 next 回退的错误。用 26 个字母随机生成的用例几乎全是”第一位就不匹配”，测不出东西。

四、Rabin-Karp：滚动哈希与”命中后必须逐字验证”

ph = (ph * BASE + p[i]) % MOD;  sh = (sh * BASE + s[i]) % MOD;      /* 初始窗口 */
if (sh == ph && std::equal(p.begin(), p.end(), s.begin() + i)) hits.push_back(i);
sh = ((sh + MOD - (unsigned long long)s[i] * h % MOD) * BASE + s[i + m]) % MOD;   /* 滚动 */

三个要点：

哈希相等只是候选，必须逐字节确认——否则就是被哈希碰撞打穿的安全漏洞（很多”用哈希校验文件”的实现栽在这里）。
减法要 + MOD 再取模，无符号数下溢会得到天文数字。
它的真正价值是二维/多模匹配（图像模板、日志指纹）和”哈希集合一次比对多个模式”，一维单串场景通常打不过 KMP 或库实现。

本机对拍结果与暴力/KMP 完全一致。

五、实测：KMP 到底比暴力快多少

50 万随机字母 + 5 字符模式：

暴力 1.50 ms | KMP 0.65 ms | std::string::find 0.43 ms

刻意构造的”最坏情况”（20 万个 a 的文本，模式是 200 个 a 加一个 b，长度 201）：

暴力 1.97 ms | KMP 0.38 ms

理论上是 O(n·m) = 4000 万次比较，实测只慢 5 倍。 原因：暴力的内层比较走的是 std::equal/memcmp，被向量化成一次 16–32 字节的批量比较，等效常数比 KMP 的单字符比较低得多。

所以诚实的结论是：

KMP 的价值是”最坏情况有保证”（O(n+m)），在对抗性输入（用户可控的搜索串、被恶意构造的日志）下不会退化。这是安全与可用性属性，不是速度属性。
日常搜索直接用 std::string::find——本机它是最快的（0.43ms），libstdc++ 用的是 Boyer-Moore/Galil 混合 + 向量化。
只有”必须自己实现、且要最坏情况保证”（面试、嵌入式、对抗输入）才手写 KMP。

六、多模式匹配：AC 自动机快 43 倍

200 个模式串扫 20 万字符文本，两种做法：

/* A：逐个跑 KMP */
for (auto &p : pats) total += kmp_find(text, p).size();
/* B：Aho-Corasick（字典树 + fail 指针），文本只扫一遍 */
ac.count(text, pats.size());

200 个模式各跑一遍 KMP 146.34 ms | AC 自动机扫一遍 3.42 ms（总命中 30699 vs 30699）

43 倍，且命中总数完全一致（30699 = 30699，这个交叉验证不是零命中糊弄过去的）。

复杂度：KMP 逐个是 O(文本长 × 模式数)，AC 是 O(文本长 + 所有模式长之和 + 命中数)。AC 自动机就是把 KMP 的”失配回退”推广到字典树上的 fail 指针，理解了 KMP 就理解了它。

现实用途：敏感词过滤、SNORT/Suricata 类入侵检测的多规则匹配、日志里同时找上百个特征串、编译器里多关键字的词法分析。这类场景没有 AC 就根本做不动。

实现上两个技巧（本机代码都用了）：

t[u].nxt[c] 在构建时直接补全成 fail 转移（if (!v) t[u].nxt[c] = t[t[u].fail].nxt[c];），查找时一次数组访问，不再 while 回退——这是 AC 常数小的关键。
统计命中数时若沿 fail 链累加，最坏会退化；要精确计数应把 out 沿 fail 树做前缀和/并集压缩。上面的实现对 200 个 4 字符模式够用，规模大时要改。

七、还该知道的两个结构

字典树（Trie）：前缀查询 O(模式长)，与数据量无关。自动补全、IP 段路由前缀匹配、拼写检查。空间是硬伤——纯 int nxt[26] 每节点 104 字节，中文要先做字符映射，或者用双数组 Trie（DAT）/ 压缩 Trie（radix tree）省一个数量级。

后缀数组 / 后缀自动机：处理”任意子串”问题（最长重复子串、不同子串数、模式匹配计数）。构建 O(n log n) 或 O(n)，比后缀树好写省内存。竞赛和生物信息常用，工程里少见。

八、这一节的自查清单

循环条件里不放 strlen/size() 之类的调用，先取到局部变量
性能测试固定优化级别，并记录它（-O0 和 -O2 差 200 倍不奇怪）
KMP 找到匹配后要 k = nxt[k-1] 才能找重叠出现
next 数组用”最长真前缀=真后缀”的定义手算三五个值自检
哈希匹配必须逐字节二次确认
随机对拍用小字母表 + 短串，制造部分匹配
普通搜索优先 std::string::find，别为了”学过 KMP”手写更慢的实现
多模式一律 AC 自动机，别循环调用单模式匹配
Trie 的节点大小要算账，中文/大字母表要用压缩或双数组变体

下一节讲树：二叉树三种遍历的递归与非递归写法、BST 的退化与旋转、AVL 与红黑树的取舍，以及 B+ 树为什么是数据库的默认选择。