第 5 章 · 02 字符串基础（对应 docs/string/）

第 5 章 · 02 字符串基础（对应 docs/string/）

本节定位：对应 OI Wiki docs/string/（共 22 篇）。难度：进阶。前置依赖：C++ STL（string/vector/队列）、第 5 章 · 01 节 DP 基础（部分字符串算法用到 DP 思想）。本节是非难点导读节，把字符串算法按"单串匹配 → 多串匹配 → 后缀结构"串起来，KMP 和 Trie 是后续 AC 自动机、SAM 的地基。

⚠️ 注意：字符串算法的代码普遍"短而精"，但思想跨度极大。KMP 的 fail 数组、AC 自动机的 fail 指针构造，光看代码很难懂，必须结合 Wiki 的图示。本节只导航，不重写。

知识地图

docs/string/ 22 篇按"从简单到复杂、从单串到后缀"排序如下。

第一站：字符串哈希（docs/string/hash.md）

把子串映射成整数，O(1) 比较两段子串是否相同。是字符串题的"万能胶"，匹配、去重、二分最长公共子串都能用。

• 多项式哈希：h[i] = (h[i-1] * B + s[i]) mod P，B 取 131 等质数，P 取大质数（如 1e9+7、1e9+9）。任意子串 [l,r] 的哈希 O(1) 算出：h[r] - h[l-1] * B^(r-l+1)。
• 自然溢出：用 unsigned long long 自然溢出代替取模（相当于 mod 2^64），速度快，但可被构造数据卡（Thue-Morse 串等反例）。
• 双哈希：用两组不同的 (B, P) 同时哈希，极大降低碰撞概率，比赛首选。

💡 学习提示：哈希是字符串题的"万能胶"，匹配、去重、二分最长公共子串都能用。但务必用双哈希，单哈希在正式赛极易被卡。哈希 + 二分求最长公共前缀是一个常见套路。

第二站：KMP（docs/string/kmp.md）—— 必会，AC 自动机的地基

单模式串匹配，O(n + m)。核心是 next/fail 数组：fail[i] 表示模式串前 i 个字符中，"最长的既是真前缀又是真后缀"的长度。

• 用途：在一个长文本里找模式串所有出现位置。
• 难点：fail 数组的构造本身用了"自匹配"思想——模式串自己跟自己匹配，这是理解 KMP 的关键。

模式串 ababaca 的 fail 数组（下标从1）：
位置:  1 2 3 4 5 6 7
字符:  a b a b a c a
fail:  0 0 1 2 3 0 1
​

⚠️ 注意：很多人把 fail 数组背成"前缀函数"就跳过了，但它的"自匹配构造"（j = fail[j] 回跳）是 AC 自动机 fail 指针的直接来源，这里没懂后面 AC 自动机一定学不动。

第三站：Trie 字典树（docs/string/trie.md）—— 必会，AC 自动机的地基

前缀树。把若干字符串按公共前缀组织成树，插入和查询都是 O(L)（L 是串长）。空间复杂度 O(总字符数)。

• 经典应用：单词查找、自动补全、最长公共前缀、异或字典树（把数字按二进制插入 Trie，求最大异或和，贪心走相反位）。
• 节点结构：ch[26] 子指针 + is_end 标记（也可加 cnt 计数）。
• Trie 是 AC 自动机的基础，也是后缀结构（如后缀自动机的转移）的简化版。

第四站：AC 自动机（docs/string/ac-automaton.md）—— 多模式串匹配

Trie + KMP 的 fail 指针。在 Trie 上给每个节点建一个 fail 指针（指向"当前串的最长真后缀对应的 Trie 节点"），就能在一个文本里同时匹配多个模式串。

• 难点：fail 指针的构造用 BFS——按层遍历 Trie，每个节点的 fail 由父节点的 fail 决定。具体地，对于节点 u 的字符 c 子节点 v，fail[v] = trans[fail[u]][c]（不断沿 fail 跳直到有 c 转移或到根）。
• 典型题：给定 n 个模式串和一个文本，问每个模式串出现几次。
• 进阶：AC 自动机上 DP（如"长度为 m、不包含任何模式串的串个数"），把 fail 树当状态转移图用。

⚠️ 注意：学 AC 自动机前必须先懂 KMP（fail 思想）和 Trie（数据结构），否则就是空中楼阁。这两个不牢，AC 自动机的 fail BFS 会完全看不懂。

第五站：Manacher 马拉车（docs/string/manacher.md）

求最长回文子串，O(n)。朴素中心扩展是 O(n²)，Manacher 的两个核心技巧：

1. 插入分隔符（如 #），把奇偶长度的回文统一成奇数长度处理。
2. 利用已拓展的右端点：维护当前能拓展到的最右回文 r 和中心 mid，新位置若在 r 内，可利用对称性直接初始化答案，避免重复扩展。

第六站：后缀数组 SA（docs/string/sa.md）

把字符串的所有后缀排序，得到 sa 数组（排名对应原位置）和 height 数组（相邻排名后缀的 LCP，最长公共前缀）。

• 用途：最长重复子串（height 最大值）、不同子串个数（Σ len - sa[i] - height[i]）、多串公共子串（连接后用 height）。
• 构造：朴素 O(n² log n)，倍增 O(n log² n) 或 SA-IS O(n)。
• SA 是 SAM 的"姊妹结构"：SA 离线排序，SAM 在线构建，第 5 章 · 03 节会对比两者。

💡 学习提示：SA 的 height 数组是精髓。掌握"height + 单调栈"能解大量"重复子串"类问题，是后缀家族的核心工具。

字符串算法与典型题对照

学习建议

1. 必会清单：字符串哈希（双哈希）、KMP（含 fail 自匹配构造）、Trie。这三个是地基，AC 自动机和后续后缀结构都建立在它们之上。
2. AC 自动机的学法：先把 KMP 的 fail 构造手推一遍，再把 Trie 画出来，最后看 fail 指针的 BFS——按这个顺序就不晕。AC 自动机本质是"Trie 上跑 KMP"。
3. 配合图示：KMP 和 AC 自动机的 Wiki 页面都有状态转移图，一定要对着图看代码，纯读代码极易劝退。手推一个 6-8 字符的小例子胜过看十遍博客。
4. 读 Wiki 顺序：hash.md → kmp.md → trie.md → ac-automaton.md → manacher.md → sa.md。其中 kmp.md 和 trie.md 是绝对核心，花再多时间也值得。
5. 后缀结构留到后面：SA 和本节末尾的 SAM（第 5 章 · 03 节）属于"后缀家族"，建议学完上面的基础再啃。后缀家族是字符串章节的顶峰。
6. 异或 Trie 是隐藏重点：docs/string/trie.md 里的异或 Trie（数字按二进制插入，求最大异或和）是高频考点（P4551 最长异或路径），别只学单词查找那部分。

💡 学习提示：字符串算法"看着像暴力优化"，但每个优化都有严密的数学背景。建议每学一个，都在纸上手推一个 6-8 字符的小例子，比看十遍博客管用。

本节要点

• 字符串哈希（双哈希）是万能工具，KMP 和 Trie 是地基。
• KMP 的 fail 数组"自匹配构造"是 AC 自动机 fail 指针的直接来源，必须吃透。
• AC 自动机 = Trie + KMP fail，多模式串匹配利器，先学 KMP 和 Trie 再学它。
• Manacher 求最长回文子串 O(n)，后缀数组 SA 是后缀家族的离线版。
• 本节是导读，深入推导见 docs/string/ 各页面；后缀结构的顶峰 SAM 在下一节精讲。