🧵 第九部分：字符串算法
从「逐字符比较」到线性时间的精妙加速。KMP、Trie、Manacher、Z 函数与 AC 自动机——覆盖 USACO Silver 至 Gold 的字符串核心。
📚 5 章 · ⏱️ 预计 2-3 周 · 🎯 目标：达到 USACO Gold 水平
第九部分：字符串算法
预计用时：2-3 周
字符串是竞赛编程中一类独特的题目：数据就是一个字符数组，但暴力做法往往在 N = 10⁵、10⁶ 量级下超时。本部分教你把「已经比较过的信息」留下来反复利用，把 O(N × M) 的朴素匹配压到 O(N + M) 甚至 O(N)。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 9.1 章 🥉 | 字符串基础 | 概念、读入、string 操作、连续段 |
| 第 9.2 章 🥈→🥇 | 字符串匹配：前缀函数与 KMP | 失配时利用已匹配前缀跳转，O(N + M) |
| 第 9.3 章 🥈 | Trie 树 | 用路径表示字符串，共享前缀，O(|s|) 查询 |
| 第 9.4 章 🥇 | Manacher 与 Z 函数 | 镜像加速——最右回文 / 最右 Z-box |
| 第 9.5 章 🥇 | AC 自动机 | Trie + fail 指针，多模式串同时匹配 |
学完本部分后能解决什么问题
-
USACO Silver：
- 单模式串匹配、子串查找与计数（KMP）
- 字符串集合查询、前缀检测、前缀冲突（Trie）
- 01-Trie 求最大异或对
-
USACO Gold：
- 最长回文子串、回文计数（Manacher）
- 后缀与前缀的匹配统计（Z 函数）
- 多模式串同时出现统计（AC 自动机）
引入的关键算法
| 技术 | 章节 | 时间复杂度 | 典型场景 |
|---|---|---|---|
| 前缀函数 / KMP | 9.2 | O(N + M) | 单模式匹配、最短周期、border |
| Trie | 9.3 | O(|s|) | 集合查询、前缀检测 |
| 01-Trie | 9.3 | O(N log W) | 最大异或对 |
| Manacher | 9.4 | O(N) | 最长回文、回文计数 |
| Z 函数（扩展 KMP） | 9.4 | O(N) | 后缀 vs 前缀统计 |
| AC 自动机 | 9.5 | O(|T| + Σ|P| + 匹配) | 多模式串同时匹配 |
本部分学习建议
- 第 9.1 章（基础） 是本章表里唯一的 Bronze 章——string 操作和连续段思想是后面所有章节的地基。
- 第 9.2 章（KMP） 是一切算法章的基础——前缀函数的「失配回退」思想会在第 9.5 章 AC 自动机的 fail 指针中原样复现。
- 第 9.3 章（Trie） 代码短、模板性强，先掌握普通 Trie 再学 01-Trie。
- 第 9.4 章的 Manacher 与 Z 函数共享同一核心：维护「当前最靠右的已知区间」，用镜像避免重复比较。
- 第 9.5 章（AC 自动机） = 第 9.3 章的 Trie 骨架 + 第 9.2 章的 fail 思想。学完前两章再看它会非常自然。
与其他部分的联系
- 字符串哈希（第 3.7 章）：哈希也能 O(N + M) 做匹配，代码更短但有冲突风险；KMP 精确无冲突，两者常互为备选。
- 贪心与 DP：KMP 的 border 结构常与 DP 结合（周期问题、循环节统计）。
- 图论：AC 自动机上沿 fail 指针的跳转构成一棵树，fail 树上的子树统计会用到位图算法部分的技巧。
💡 核心思路： 字符串算法的通用套路是「拼接 + 分隔符」——把模式串和文本用
#拼起来，一个前缀函数 / Z 函数同时看到两边的信息。这个技巧在 9.2、9.4、9.5 反复出现。