字符串大学习

少女樂隊_GirlsBand · 2026-10-22 08:58:56 · 算法·理论

字符串大学习

前言

本文章使用 LLM 辅助生成，如有错误，请在评论区指出。感谢！

食用建议：根据自己的水平和需求，从大纲中选取需要学习的部分跳转学习。不建议从头通读。

目录

• 0. 引言：字符串问题的两副面孔　—　两条主线（匹配 / 压缩）+ fail 树暗线 + 选型速查
• 1. 记号与基础　—　六个记号、border 理论、border↔周期等价
• 2. 字符串哈希　—　O(1) 子串查询、错误率、卡法与防御
• 3. Trie 字典树　—　基础 / 01-Trie / 合并 / 可持久化 / Trie 图
• 4. KMP 与前缀函数　—　求 \pi、用 \pi 匹配、fail 树（全书主线）
• 5. Z 函数与扩展 KMP　—　最右匹配段、镜像复用
• 6. Manacher　—　奇偶统一、半径还原、回文计数
• 7. 字符串匹配综合：五把武器怎么选　—　决策表与选型原则
• 8. AC 自动机　—　fail 指针、Trie 图、fail 树、AC 上 DP
• 9. 后缀数组　—　倍增构造、height、五个经典应用
• 10. 后缀自动机（SAM）　—　endpos、extend/clone、parent 树
• 11. 广义 SAM　—　多串建 SAM 的两种正确做法
• 12. 回文自动机（PAM）　—　两棵扩展树、fail 树、series link
• 13. 子序列自动机　—　下一个字符表、本质不同子序列计数
• 14. 后缀树与后缀平衡树　—　压缩后缀 Trie、动态维护后缀序
• 15. Lyndon 分解与最小表示法　—　Duval 算法、双指针
• 16. Main-Lorentz 算法　—　O(n\log n) 求全部平方串
• 17. 字符串算法库：封装与取舍　—　模板选择与常数
• 18. Trick 五维全览　—　33 条（A1–A12 / B1–B9 / C1–C12）+ E 维度 26 条
• 19. 题单总索引　—　按知识点索引 + 按经典度排序 + 扩充补漏
• 20. 总结提升　—　十五个结构的一句话本质 + 五条主线
• 21. 速通指南　—　一下午 / 一天 / 两天 + 十六问自测

配套图：img/ 目录下 26 张 SVG/PNG，每张对应一个结构或过程。

0. 引言：字符串问题的两副面孔

0.1 一个让人卡住的问题

给一个长度 10^6 的文本串 S，和一个长度 10^5 的模式串 T，问 T 在 S 中出现了几次、分别在哪些位置。

最直接的做法是枚举起点，逐位比较：

For(i, 1, n - m + 1) {
    bool ok = true;
    For(j, 1, m) if (S[i + j - 1] != T[j]) { ok = false; break; }
    if (ok) ans.push_back(i);
}

最坏 O(nm)=10^{11}，一秒只能跑 10^8 次基本操作，要跑一千秒。

慢在哪？ S=\texttt{aaaaaaab}，T=\texttt{aaab}。i=1 比较 4 次失败，i=2 又从头比较 4 次失败……每次失败后，我们已经知道了 S 中那一段是 aaa，这个信息被完全丢弃。O(nm) 的浪费就在重复读已经读过的字符。

0.2 第二类问题：子串太多

给串 s（|s|\le10^6），求它有多少个本质不同的子串。

朴素想法：枚举 O(n^2) 个子串，哈希表去重。n=10^6 时是 5\times10^{11} 个子串，完全不可行。

注意"子串 = 某个后缀的前缀"。若两个后缀的 LCP 是 L，它们共同贡献了 L 个重复子串。所以

而"前面已出现的最大 LCP"要求把所有后缀排好序——这就逼出了后缀数组。另一条路是把"所有子串"直接压成 O(n) 个状态，即后缀自动机。

0.3 全书地图：两条主线

字符串问题分成两类，对应本书的两部分：

第一类：匹配问题（第一部分，第 1–7 章）——"一个串在另一个串里出现没有、在哪、几次"。

这五把武器有一个共同思想：

用已经算好的、位于当前位置左边的信息，推当前答案。

KMP 用 \pi_{i-1} 推 \pi_i；Z 函数用最右匹配段推 z_i；Manacher 用镜像点的半径推当前半径。理解这句话，后面几个算法都不用死记——可以现场重新推出来。

第二类：压缩问题（第二部分，第 8–17 章）——"把 O(n^2) 个子串压成 O(n) 个结构"。

                    ┌─ AC 自动机（多串的前缀树 + fail）
                    │
    Trie ───────────┼─ 后缀树（所有后缀的前缀树 = 压缩后缀 Trie）
     │              │
     │              └─ 回文自动机（所有回文的两侧扩展树）
     │
     ├─ 后缀数组（排序所有后缀）
     │
     └─ 后缀自动机（endpos 等价类）

    Lyndon 分解 ──► 最小表示法、平方串

四条最关键的依赖链：

1. Trie → AC 自动机 → fail 树。AC 自动机是"多模式串的 Trie + 每个节点指向最长真后缀的指针"。fail 指针构成的树让"统计出现次数"变成"子树求和"。
2. 后缀排序 → height 数组 → LCP 查询。SA 把"子串问题"变成"后缀区间问题"，height 把"LCP"变成"区间最小值"。
3. endpos 等价类 → SAM → parent 树。SAM 每个状态是一批 endpos 相同的子串，parent 树刻画包含关系。
4. Lyndon 分解 → 最小表示法 → 平方串。Duval 算法一个 O(n) 的双指针同时解决三件事。

0.4 贯穿全书的一条暗线：fail 树

这是本书最重要的一条线索，先点明，后面反复回扣。

把"失配指针"当父亲建树，得到一棵树。四类结构都有这棵树：

四棵树的节点含义不同，形状和用法完全一致。所以 §4.9 不是"KMP 的一个应用"，而是后面三个自动机的样板：

• 想知道"某模式串出现了几次" → 找 fail 树，求子树和；
• 想知道"两个串的最长公共后缀" → 求 LCA；
• 想统计"有多少状态满足某条件" → DFS 序 + 树状数组。

0.5 选型速查

0.6 记号与前置换算

一个重要事实：正文的下标全部 1-based，但代码里 0-based。这个差异是大量 off-by-one 错误的来源，下文代码注释会标出。

1. 记号与基础

1.1 字符串的六个记号

后面全篇只用这几个记号，先一次说清。

定义：设 s 是一个长度为 n 的字符串，下标从 1 开始。

• 子串 s[l..r]：从第 l 个字符到第 r 个字符连续取出的一段，长度 r-l+1。例如 s=\texttt{abcde} 时 s[2..4]=\texttt{bcd}。
• 前缀 s[1..i]：从开头取 i 个字符。s 的真前缀指 i<n 的前缀。
• 后缀 s[i..n]：从第 i 个字符取到末尾。s 的真后缀指 i>1 的后缀。
• border：一个既是 s 的真前缀、又是 s 的真后缀的字符串。说"s 有长度为 r 的 border"，指 s[1..r]=s[n-r+1..n] 且 r<n。
• 周期 p：若对所有 1\le i\le n-p 都有 s_i=s_{i+p}，称 p 是 s 的周期。
• LCP（Longest Common Prefix）：两个串的最长公共前缀的长度。

注意 border 与周期的关系，这是全篇最重要的一条等价：

验证：s=\texttt{ababa}，n=5。它有长度 3 的 border（aba），所以 5-3=2 应该是周期。检查：s_1=s_3=\texttt{a}、s_2=s_4=\texttt{b}、s_3=s_5=\texttt{a}，成立。反方向也一样：周期 p 意味着 s_i=s_{i+p}，把 i=1..n-p 的等式串起来，就得到 s[1..n-p]=s[p+1..n]，即长度为 n-p 的 border。

这条等价把"前后缀相等"和"平移后自重合"两种完全不同的直觉联系起来。后面求最小循环节、判周期串，用的都是它。

1.2 字符集与编码

定义：字符集是字符串中允许出现的字符的集合，记作 \Sigma。竞赛里常见的三种：

| 字符集 | 大小 |\Sigma| | 处理方式 | | ---------- | --------------- | --------------------- | | 小写字母 | 26 | 直接 c - 'a' 当下标 | | 可见 ASCII | 95 | 直接 c - ' ' 当下标 | | 任意整数 | 10^9 | 必须离散化或哈希 |

为什么 e 要点出字符集：因为它直接决定 Trie 和 AC 自动机的空间。Trie 每个节点要开 |\Sigma| 个儿子指针，字符集是 26 时 \sum|s|=3\times10^5 需要 3\times10^5\times26\times4\text{B}=31\text{MB}（勉强）；字符集是 10^9 时根本开不下，必须换成 map 或"只在用到的边上开点"。

一条实用建议：读入字符串时统一转成 1 到 |\Sigma| 的整数存进 int 数组。这样后面所有算法都不用再碰 char，也避免了字符集大小不固定带来的麻烦。

// 统一转成 1..k 的整数，k 由题目给定
int n; int a[N];
string s; cin >> s; n = s.size();
For(i, 1, n) a[i] = s[i - 1];              // 直接用 ASCII 值当字符集，k = 256

1.3 朴素匹配与它的复杂度

先把第 0 章那个朴素做法分析清楚，后面每一把武器都是相对它改进。

定理：朴素匹配的最坏复杂度是 \Theta(nm)。

证明：取 S=\texttt{a}^n\texttt{b}、T=\texttt{a}^m\texttt{b}（m\le n）。对每个起点 i，都要比较 m 次才失败（最后一位不同），共 n-m+1 个起点，总比较次数 (n-m+1)m。取 m=\lceil n/2\rceil 得 \Theta(n^2)。\square

证明要点：最坏情况的构造方式是"每次都匹配到最后一位才失败"。

适用边界：随机数据下朴素匹配是 O(n) 的（平均只要比较 1–2 次就失配），所以很多暴力能水过——但出题人可以轻松构造数据卡掉它。

相关例题　P3375 【模板】KMP · P4824 Censoring S · CSES-1753 String Matching

1.4 Trie：把公共前缀合并

Trie 属于"结构"类工具，在数据结构卷已经详细讲过，这里只说它在字符串问题里的位置。

核心观察：如果一堆字符串共享前缀，那么"前缀"这个部分只需要存一次。

证明要点：高位权重大于所有低位之和，所以"先保证高位能取 1"必然最优——与线性基的贪心是同一个论证。

实测（脚本第 2 项）：数字组 \{3,10,5,25,2,8\}，最大异或对 =28，与 O(n^2) 暴力一致 ✓。

求"第 k 小异或值"

需要每个节点的子树大小（sz）。当前位尝试走 0 分支，若 k\le sz_0 就走 0，否则 k\leftarrow k-sz_0 走 1。

// 在 01-Trie 中求与 x 异或的第 k 小值（k 从 1 开始）
int query_kth(int x, int k) {
    int u = 1, res = 0;
    Rof(i, LG, 0) {
        int b = (x >> i) & 1;
        // 先考虑能让这一位为 0 的分支：与 x 同位
        if (ch[u][b] && sz[ch[u][b]] >= k) u = ch[u][b];
        else {
            if (ch[u][b]) k -= sz[ch[u][b]];
            res |= 1 << i;                       // 这一位贡献 1
            u = ch[u][b ^ 1];
        }
    }
    return res;
}

注意：这里的"第 k 小"是在异或值上排序，不是在原数上。所以遍历时是"优先让异或结果的当前位为 0"。

01-Trie 与线性基的分工

判据：问"两个数的异或"用 01-Trie；问"子集的异或"用线性基。两者不能互替。

例题：P4551 最长异或路径

题意：给 n 个点的带权树（n\le10^5，边权 <2^{31}），求树上所有路径中"边权异或和"的最大值。

关键转化：路径异或和 = 两个点到根的前缀异或和的异或。

第一步：为什么。设 d_u 为根到 u 的路径异或和。对路径 u\to v（设 w=\operatorname{lca}(u,v)）：

因为 d_w 出现两次，异或抵消。

第二步：问题转化。于是"求路径异或最大值"变成"在数组 d_1..d_n 中求两数异或的最大值"——这是 01-Trie 的标准问题。

第三步：01-Trie。把 d_i 全部插入 01-Trie（LG=30，因为边权 <2^{31}，路径异或和也 <2^{31}），然后对每个 d_i 查询"与它异或最大的值"，取最大值。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, LG = 30;
struct Edge { int to; int w; };
vector<Edge> e[N];
int d[N];
int ch[N * 32][2], tot = 1;

void insert(int x) {
    int u = 1;
    for (int i = LG; i >= 0; -- i) {
        int b = (x >> i) & 1;
        if (!ch[u][b]) ch[u][b] = ++ tot;
        u = ch[u][b];
    }
}
int query_max(int x) {
    int u = 1, res = 0;
    for (int i = LG; i >= 0; -- i) {
        int b = (x >> i) & 1, want = b ^ 1;
        if (ch[u][want]) res |= 1 << i, u = ch[u][want];
        else u = ch[u][b];
    }
    return res;
}
void dfs(int u, int fa, int cur) {
    d[u] = cur;
    for (auto ed : e[u]) if (ed.to != fa)
        dfs(ed.to, u, cur ^ ed.w);
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i < n; ++ i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0, 0);
    for (int i = 1; i <= n; ++ i) insert(d[i]);
    int ans = 0;
    for (int i = 1; i <= n; ++ i) ans = max(ans, query_max(d[i]));
    printf("%d\n", ans);
    return 0;
}

样例验证：树 1{-}2(3)、2{-}3(4)、2{-}4(6)，答案 7（路径 1\to3：3\oplus4=7）✓。

复杂度：DFS O(n)，插入与查询各 O(n\cdot LG)。总 O(n\cdot LG)。空间 O(n\cdot LG) 个节点。

点评："路径异或和转成两点前缀异或"这个技巧是本题的灵魂，它把树上问题拍平成了数组问题。同类题还有"树上路径计数异或和为定值"，也是这个转化 + Trie 计数。

3.5 01-Trie 合并

01-Trie 合并：同向子树递归合并，节点权值相加 问题：有两棵 01-Trie（或同一棵树的多个子树），要把它们合并成一棵。

做法：递归合并。设合并 u（来自 A）与 v（来自 B）：

• 若 u 或 v 为空，直接返回另一个；
• 否则合并 u 的左儿子与 v 的左儿子、右儿子与右儿子，sz[u] += sz[v]。

// 01-Trie 合并：把 v 合并进 u，返回合并后的根
int merge(int u, int v) {
    if (!u || !v) return u | v;
    sz[u] += sz[v];
    ch[u][0] = merge(ch[u][0], ch[v][0]);
    ch[u][1] = merge(ch[u][1], ch[v][1]);
    return u;
}

复杂度：O(\text{重叠节点数})。因为只有两边都非空的节点才会继续递归，而每个节点最多被"消耗"一次。

总复杂度（树上合并场景）：若每个叶子初始贡献 O(LG) 个节点，总共 O(n\cdot LG) 个节点，全部合并的总额外代价是 O(n\cdot LG)——均摊线性。

典型用途：树上启发式合并（DSU on Tree）的替代品、线段树合并的"值域为二进制"版本。

相关例题　P6072 『MdOI R1』Path · P6018 [Ynoi2010] Fusion tree

3.6 可持久化 01-Trie

版本 1 插入 1（二进制 01），版本 2 插入 2（二进制 10）。橙色是版本 2 新建的三个节点；加粗边框的「0」节点由两个版本共用——版本 2 的根直接指向它，没有复制。虚线小方块是空儿子。

问题：给序列 a_1..a_n，多次询问"区间 [l,r] 内与 x 异或的最大值"。

朴素做法：对每个询问重建 Trie，O(n\cdot LG) 每次，不可行。

关键想法：像主席树一样，对每个前缀建一个 Trie 版本；查询 [l,r] 时用"版本 r 减去版本 l-1"的节点计数差判断某个分支是否在区间内存在。

建树：插入 a_i 时，从版本 i-1 的根开始，沿途所有节点都复制一份，把改变的路径上的 cnt 加 1。

int ch[N * 32][2], cnt[N * 32], rt[N], tot;

// 在版本 o 的基础上插入 x，返回新版本根
int insert(int o, int x) {
    int root = ++ tot, u = root;
    cnt[u] = cnt[o] + 1;
    Rof(i, LG, 0) {
        int b = (x >> i) & 1;
        int &nxt = ch[u][b];                     // 新版本的这一支
        int old = ch[o][b];                      // 旧版本的这一支
        nxt = ++ tot;
        ch[nxt][0] = ch[old][0];                 // 先整份复制
        ch[nxt][1] = ch[old][1];
        cnt[nxt] = cnt[old] + 1;
        u = nxt, o = old;                        // 继续往下
    }
    return root;
}

// 在 (L-1, R] 版本差中查询与 x 异或最大的值
int query(int L, int R, int x) {
    int u = rt[L - 1], v = rt[R], res = 0;
    Rof(i, LG, 0) {
        int b = (x >> i) & 1, want = b ^ 1;
        // 判断 want 分支在区间内是否有数
        if (cnt[ch[v][want]] - cnt[ch[u][want]] > 0) {
            res |= 1 << i;
            u = ch[u][want], v = ch[v][want];
        } else {
            u = ch[u][b], v = ch[v][b];
        }
    }
    return res;
}

为什么"版本差"能表示区间：版本 k 记录了 a_1..a_k 的全部信息（每个节点的 cnt 是"a_1..a_k 中有多少个数经过这个节点"）。所以 cnt[版本 R] - cnt[版本 L-1] 就是"a_L..a_R 中有多少个数经过这个节点"——正是区间内的计数。

复杂度：建树 O(n\cdot LG) 时间与空间（每次插入新增 LG+1 个节点），单次查询 O(LG)。

实测（脚本第 6 项）：数组 [5,3,9,7,2]，询问区间 [2,4] 与 x=6，可持久化 Trie 得 15，暴力 \max(3\oplus6,9\oplus6,7\oplus6)=15 ✓。

注意：可持久化 Trie 的空间是 O(n\cdot LG) 个节点，n=10^5、LG=30 时是 3.1\times10^6 个节点——*要开 `int ch[N32][2]` 这种规模**，别开小了。

例题：P4735 最大异或和

题意：给序列 a_1..a_n（n,m\le3\times10^5，a_i<2^{24}），支持两种操作：

1. 在末尾追加一个数（序列变长）；
2. 给定 l,r,x，求 \max_{l\le p\le r}\bigl(a_p\oplus a_{p+1}\oplus\cdots\oplus a_N\oplus x\bigr)，其中 N 是当前序列长度。

关键转化：后缀异或和 = 两个前缀异或和的异或——把它变成"区间内与 x 异或最大"。

第一步：化简。 设 s_i=a_1\oplus\cdots\oplus a_i（s_0=0）。则

所以要求的式子是

其中 q=p-1。于是问题变成：在 s_{l-1},s_{l},\ldots,s_{r-1} 中找一个与定值 c=s_N\oplus x 异或最大的。

第二步：可持久化 01-Trie。 对每个前缀异或和 s_i 建一个 Trie 版本（版本 i 含 s_0..s_i）。查询区间 [l-1,r-1] 时用

判断某个分支在区间内是否存在。

第三步：追加操作。 直接在最新版本上继续插入即可（就是 extend）。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, LG = 30, M = N * (LG + 2);
int ch[M][2], cnt[M], rt[N], tot;
int n, m, s[N];

int insert(int o, int x) {                 // 在版本 o 上插入 x
    int root = ++ tot, u = root;
    cnt[u] = cnt[o] + 1;
    for (int i = LG; i >= 0; -- i) {
        int b = (x >> i) & 1;
        int nxt = ++ tot;
        ch[nxt][0] = ch[ch[o][b]][0];
        ch[nxt][1] = ch[ch[o][b]][1];
        cnt[nxt] = cnt[ch[o][b]] + 1;
        ch[u][b] = nxt;
        u = nxt, o = ch[o][b];
    }
    return root;
}
int query(int L, int R, int x) {           // 在版本 (L, R] 中查与 x 异或最大
    int u = L, v = R, res = 0;
    for (int i = LG; i >= 0; -- i) {
        int b = (x >> i) & 1, want = b ^ 1;
        if (cnt[ch[v][want]] - cnt[ch[u][want]] > 0) {
            res |= 1 << i; u = ch[u][want], v = ch[v][want];
        } else u = ch[u][b], v = ch[v][b];
    }
    return res;
}
int main() {
    scanf("%d%d", &n, &m);
    rt[0] = insert(0, 0);                  // 版本 0 含 s_0 = 0
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &s[i]); s[i] ^= s[i - 1];
        rt[i] = insert(rt[i - 1], s[i]);
    }
    int len = n;
    while (m --) {
        char op[2]; scanf("%s", op);
        if (op[0] == 'A') {
            int x; scanf("%d", &x);
            ++ len; s[len] = s[len - 1] ^ x;
            rt[len] = insert(rt[len - 1], s[len]);
        } else {
            int l, r, x; scanf("%d%d%d", &l, &r, &x);
            // a[p]^..^a[len] = s[len] ^ s[p-1]
            // p in [l,r]  =>  q = p-1 in [l-1, r-1]
            // 在 s[l-1 .. r-1] 中找与 (s[len] ^ x) 异或最大
            // 版本 (l-1)-1 = l-2 到 r-1；l=1 时左端用空版本（rt 索引 0 表示"无"）
            int Lv = (l >= 2) ? rt[l - 2] : 0;
            printf("%d
", query(Lv, rt[r - 1], s[len] ^ x));
        }
    }
    return 0;
}

复杂度：每次插入 O(LG)，每次查询 O(LG)，空间 O((n+m)\cdot LG)。

要点：三个易错位置——① 版本 0 必须先插入 s_0=0（否则左端点会把 0 漏掉）；② query 的两个版本参数是 l-2 与 r-1 对应的根，而 l=1 时左版本要用空版本；③ LG 要覆盖 s_i 的最大位——a_i\le10^7<2^{24}，但 s_N\oplus x 可能超过 2^{24}，所以取 LG=25 才安全（用 24 会 WA）。

3.7 Trie 图

Trie 图：橙色虚线为补边 ch[u][c]\leftarrow ch[fail[u]][c] 问题：AC 自动机里，从某个状态读一个字符后，若 Trie 上没有这条边，本来是"沿 fail 链往上找"。能不能把这个过程预处理掉？

做法（Trie 图 / 补全 Trie）：对每个节点 u 和每个字符 c，若 ch[u][c] 不存在，就令

ch[u][c] = ch[fail[u]][c]      （若 u 是根，则指向根自己）

这样查询时不需要跳 fail，每次 O(1) 转移。

void build_trie_graph() {
    queue<int> q;
    for (int c = 0; c < 26; ++ c)
        if (ch[1][c]) fail[ch[1][c]] = 1, q.push(ch[1][c]);
        else ch[1][c] = 1;                       // 根的缺失边指向自己
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; ++ c) {
            int v = ch[u][c];
            if (v) fail[v] = ch[fail[u]][c], q.push(v);
            else ch[u][c] = ch[fail[u]][c];      // 补边
        }
    }
}

代价：把 Trie 补成"完整自动机"，空间变成 O(\text{节点数}\times|\Sigma|)（本来稀疏，现在满了）。但查询从"可能要跳多次 fail"变成"O(1)"。

这就是 AC 自动机的标准实现（详见第 8 章）。放在这里是因为它本质上是 Trie 的一个操作。

3.8 Trie 上的 DFS 序与子树信息

核心事实：Trie 是一棵树，所以"某节点子树内的所有前缀"在 DFS 序上是连续区间。

应用一：把"前缀约束"变成"区间约束"。 例如"求以 abc 为前缀的所有串的权值和"，就是"求 DFS 序上 [\text{tin}_{abc},\text{tout}_{abc}] 区间的和"。这样就能套线段树 / 树状数组 / 莫队。

应用二：把"两个串的 LCP"变成"LCA 深度"。

其中 u_s 是 s 对应的节点。这是 Trie 最常用的性质之一。

应用三：Trie 上 DP。 若题目在 Trie 上做"选若干个串，使它们的公共前缀尽量长"，直接树形 DP。

相关例题　P5840 [COCI2015] Divljak · P3311 [SDOI2014] 数数 · P3294 [SCOI2016] 背单词

3.9 复杂度与空间

节点数上界：n 个串、串长 L，节点数 \le nL+1。实际远小于上界，因为共享前缀。

实测（脚本第 4 项）：

字符集越小，共享越多，节点越省。

3.10 实现陷阱

陷阱一：根节点编号。 用 1 作根（这样 0 可以表示"空儿子"）。若用 0 作根，ch[u][c]==0 就无法区分"没有儿子"和"儿子是根"。

int ch[N][26], tot = 1;      // tot=1，根是 1，空儿子是 0 ✓

int ch[N][26], tot = 0;      // ✘ 根是 0，与"空"冲突

陷阱二：N 开小。 节点数是 nL+1，不是 n。n=10^5、L=10^5（单个长串）时节点数是 10^5，但如果 n=10^4、L=10^4，就是 10^8——必须按 nL 估。

陷阱三：可持久化 Trie 的数组大小。 O(n\cdot LG) 个节点，n=10^5、LG=30 时要 3.2\times10^6。写成 N*2 会 RE。

陷阱四：01-Trie 的 LG 取值。 要覆盖数值的最大位。数值 \le10^9 时 LG=30 够；\le10^{18} 时要用 LG=60，且类型是 long long。

陷阱五：多组数据不清空。 用 tot = 1 重置，并对新建的节点清空 ch 数组。用 vector 版更方便（clear() 即可）。

3.11 延伸阅读（更多同知识点题目）

相关例题　P2580 于是他错误的点名开始了 · P3879 [TJOI2010] 阅读理解 · P4551 最长异或路径* · P4735 最大异或和 · P5283 [十二省联考2019] 异或粽子 · P2922 [USACO08DEC] Secret Message G · P9753 [CSP-S2023] 消消乐 · P3065 [USACO12DEC] First! G · P4407 [JSOI2009] 电子字典 · P3294 [SCOI2016] 背单词 · P4592 [TJOI2018] 异或 · P6072 『MdOI R1』Path · CF842D Vitya and Strange Lesson · CF706D Vasiliy's Multiset · CF455B A Lot of Games

习题池：Trie / 01-Trie

入门·普及

提高

省选

NOI

3.12 这一节要带走的三句话

1. Trie 把"共享前缀"变成物理共享，所以前缀查询 O(|p|)，与词典规模无关。
2. 01-Trie 是"把数当定长 01 串"的 Trie，异或最值靠"尽量走相反位"的高位贪心；求两个数的异或用它，求子集的异或用线性基。
3. 可持久化 01-Trie 用"版本差"支持区间查询，空间 O(n\cdot LG)，数组必须按这个量级开。

4. KMP 与前缀函数

4.1 动机：把"每次从头比"变成"带着信息后退"

再看一次朴素匹配的浪费。

关键观察一：\pi_i\le\pi_{i-1}+1。

证明：设 \pi_i=k>0，则 s[1..k]=s[i-k+1..i]。两边去掉最后一个字符得 s[1..k-1]=s[i-k+1..i-1]，说明 k-1 是 s[1..i-1] 的一个 border 长度，故 k-1\le\pi_{i-1}，即 k\le\pi_{i-1}+1。\square

证明要点：把等式两边各砍掉末尾一位，得到的是 i-1 处的 border。

推论：枚举下界从 i-1 降到 \pi_{i-1}+1。更进一步，只在 s_i=s_{\pi_{i-1}+1} 时才可能取到 \pi_{i-1}+1，否则继续往下。

复杂度：这样改完后字符串比较次数是 O(n)，但每次比较仍是 O(k) 的子串判等，总复杂度降到 O(n^2)。还不够。

4.4 关键观察二：失配时跳到哪

真正的问题在"往下枚举"这一步。当 s_i\ne s_{\pi_{i-1}+1} 时，\pi_i 应该是什么？

引理：设 j 是 s[1..i-1] 的一个 border 长度，且 j<\pi_{i-1}，那么 j 也是 s[1..\pi_{i-1}] 的 border 长度。

证明：j\le\pi_{i-1} 且 j 是 s[1..i-1] 的 border，所以 s[1..j]=s[i-j..i-1]。又 s[1..\pi_{i-1}]=s[i-\pi_{i-1}..i-1]。由于 j\le\pi_{i-1}，s[i-j..i-1] 正好是 s[i-\pi_{i-1}..i-1] 的后缀，也就是 s[1..\pi_{i-1}] 的后缀。所以 s[1..j] 既是 s[1..\pi_{i-1}] 的前缀又是它的后缀，即 j 是它的 border。\square

这个引理说明什么：s[1..i-1] 的所有 border 长度，构成一条链

（注意 \pi_{\pi_{i-1}-1} 是"长度 \pi_{i-1} 的前缀的 border"，因为 \pi 的下标是长度）。

所以失配时不需要从 i-2 一个个往下试，直接沿这条链跳：

直到 j=0 或 s_i=s_{j+1}。

算法：

pi[1] = 0, j = 0
for i = 2 to n:
    while j > 0 and s[i] != s[j+1]:   # 失配，沿 border 链跳
        j = pi[j]
    if s[i] == s[j+1]: j += 1
    pi[i] = j

（j 是"当前已匹配的 border 长度"，下一个待比较的字符是 s_{j+1}。注意比较对象是 s_{j+1} 而不是 s_{i+1}——s_i 是正在读入的新字符，s_{j+1} 是"接着往下要比的那一位"。）

border 链：长 6 的串失配后依次退到长 4、长 2 的 border

4.5 复杂度：为什么是 O(n)

这是 KMP 最容易被含糊过去的地方，值得严格讲。

定理：计算整个前缀函数数组的复杂度是 O(n)。

证明（势能分析）：定义势能 \Phi_i=\pi_i（第 i 步结束后的前缀函数值）。观察每次迭代 j 的变化：

• if 分支至多让 j 增加 1；
• while 循环每转一圈让 j 减少至少 1（因为 \pi_{j}<j）。

整个过程中 j 从 0 出发，最多增加 n 次（每次 +1），所以它总共只能减少 n 次。因此 while 的总执行次数不超过 n。外层 n 次迭代，每次 O(1) 均摊，总计 O(n)。\square

证明要点：j 只增不减地"攒"，攒一次要一次 +1，所以减的总次数被增的总次数卡住。

这个论证的模式值得记住：凡是"指针只朝一个方向单调移动、每次移动都消耗某种单调量"的算法，都能用同样的方式论证线性复杂度。Z 函数、Manacher、双指针、单调栈全都用这个模式。

4.6 用 \pi 做匹配：KMP 的另一半

到这里我们只算了 \pi，还没拿它做任何事。这一节补上另一半——在文本串上找出模式串的所有出现位置。

问题：已知 T 的 \pi 数组，在 S 中定位 T 的每一次出现。

朴素做法：枚举起点 p=1..n-m+1，逐位比对，O(nm)——正是 §4.1 里被嫌弃的那个做法。

关键：把"已经匹配了多少"记成一个状态

扫描 S 时维护一个整数 j：

也就是"当前已经匹配上 T 的前 j 位"。这个 j 就是 KMP 的状态。

不变量：处理完 S_i 之后，若 j>0，则

（j=0 时等式退化为空串，平凡成立。）

为什么状态只需一个整数：因为我们要找的是"T 的某个前缀"，而前缀由长度唯一确定。长度是 j，内容就是 T[1..j]，不必额外存。

三个转移分支

读入 S_i 时：

为什么失配时是 j=\pi_j，而不是 j=0：

不变量给出 S[i-j+1..i-1]=T[1..j]。现在 S_i\ne T_{j+1}，说明"匹配 j+1 位"失败。那么长度 k<j 还有没有戏？要求

而由不变量，左边这段位于 T[1..j] 的末尾，即 S[i-k+1..i-1]=T[j-k+1..j]。所以 k 必须满足

这正是"T[1..j] 的 border"的定义。最大的那个 k 就是 \pi_j——§4.4 那条引理在这里第二次登场。

这条推理同时说明了一件事：失配时 i 不需要回退。所有该退的东西都已经在 j 里了。

为什么匹配成功后是 j=\pi_j，而不是 j=0：模式串可以重叠出现。T=\texttt{aa} 在 S=\texttt{aaaa} 中出现在位置 1,2,3。成功后清零，后两个就漏了。

走一遍

推论：\text{fail}[i]<i 恒成立（真 border 严格短于自身）。

这一条看似平凡，却是后面建树的基础：它保证了 fail 关系无环。

推论：fail 链长度 O(i)，但沿链跳的均摊代价是 O(1)——这正是 §4.5 势能分析证明的事。

4.9 fail 树（失配树）

既然 \text{fail}[i]<i 恒成立，把 fail 当成父亲指针，就得到一棵树。

定义：fail 树以 0 为根，节点 i（1\le i\le n）的父亲是 \text{fail}[i]。

为什么一定是树：每个节点 i\ge 1 恰有一个父亲 \text{fail}[i]<i，且沿父亲走严格递减，最终必到 0。有唯一根、无环、每个非根节点一个父亲——这就是树。

最关键的一条性质：

在 fail 树上，i 到根的路径（不含根）就是 T[1..i] 的全部 border。

这不是新结论，就是 §4.8 那条引理的树上说法。但它把"沿链跳"变成了"树上走路径"，于是树上的一切工具都能用。

以 T=\texttt{aabaaab} 为例，\pi=[0,1,0,1,2,2,3]，fail 树是：

0(root)
├─ 1  (a)
│  ├─ 2  (aa)
│  │  ├─ 5  (aabaa)
│  │  └─ 6  (aabaaa)
│  └─ 4  (aaba)
└─ 3  (aab)
   └─ 7  (aabaaab)

读法：节点 7（aabaaab）到根的路径是 7\to3\to0，所以它的 border 是长度 3 的 aab，没有更小的了。

节点 6（aabaaa）的路径是 6\to2\to1\to0，border 依次是 aa、a。

T=\texttt{aabaaab} 的 fail 树。每个节点是一个前缀，父边指向它的最长 border。节点旁括号内是该前缀的内容，方框数字是子树大小——也就是该前缀在 T 中的出现次数。

节点数：n+1（含根）。边数：n。建树就是 O(n) 遍历一遍 fail 数组。

4.10 fail 树上的四种操作

把 fail 树建出来后，KMP 的绝大部分应用都变成树上的标准问题。这一节把四种操作一次性讲清，后面各节只是套用。

操作一：子树和 = 出现次数

定理：前缀 T[1..i] 在 T 中的出现次数，等于 fail 树上 i 的子树大小。

证明：T[1..i] 每出现一次（结束位置为 e），就说明 T[1..e] 有一个长度为 i 的 border，即 i 在 T[1..e] 的 fail 链上，也就是 e 在 i 的子树里。反之亦然。所以"出现位置"与"子树内节点"一一对应。\square

做法：

// 建树后按编号从大到小累加（fail[i] < i，所以 i 降序即拓扑逆序）
For(i, 1, n) cnt[i] = 1;
for (int i = n; i >= 1; -- i) cnt[fail[i]] += cnt[i];
// 现在 cnt[i] = T[1..i] 的出现次数

为什么不用真的建树：因为 \text{fail}[i]<i，编号本身就是一个合法的拓扑序。按 i 从 n 降到 1 累加，等价于"从叶子往根"，不需要 DFS。

验证（T=\texttt{aabaaab}）：

操作二：深度 = border 个数

定义：\text{dep}[i]=\text{dep}[\text{fail}[i]]+1（\text{dep}[0]=0）。

这直接就是 P5829 的解法：建 fail 树，树上倍增求 LCA，O((n+m)\log n)。

// fail 树上倍增求 LCA（P5829）
const int LOG = 20;
int up[LOG][N], dep[N];

void buildTree(int n, int *fail) {
    dep[0] = 0;
    For(i, 1, n) up[0][i] = fail[i], dep[i] = dep[fail[i]] + 1;
    For(k, 1, LOG - 1) For(i, 0, n) up[k][i] = up[k - 1][up[k - 1][i]];
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    For(k, 0, LOG - 1) if (d >> k & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; -- k)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

注意：这里求的是前缀之间的最长公共 border，答案就是 LCA 的编号（编号即长度）。与通常"求最近公共祖先"不同的是，LCA 可能为 0（表示没有公共 border），此时输出 0。

例题：P5829 【模板】失配树

题意：给串 S（|S|\le10^6）和 m 次询问（m\le10^5），每次给 p,q，求"S 的前缀 p 与前缀 q 的最长公共 border"。

关键转化：失配树上的 LCA。

第一步：建失配树。 fail[i] 作为 i 的父亲，根是 0。i 到根的路径 = i 的所有 border。

第二步：答案 = LCA。 "前缀 p 与前缀 q 的公共 border"= "p 的某个 border 且是 q 的 border"= "p 的祖先且是 q 的祖先"= 公共祖先。最长的那个就是 LCA。

注意：LCA 可能恰好是 p 或 q 自己（当 p 是 q 的 border 时）。但题目通常要求"真 border"，所以要排除 p,q 本身——判断 LCA 是否等于 p 或 q，若是则取它的父亲。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, LG = 20;
char s[N];
int fail[N], fa[N][LG], dep[N];
int n, m;

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LG - 1; i >= 0; -- i)
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    for (int i = LG - 1; i >= 0; -- i)
        if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
int main() {
    scanf("%s%d", s + 1, &n); scanf("%d", &m);
    for (int i = 2, j = 0; i <= n; ++ i) {
        while (j && s[j + 1] != s[i]) j = fail[j];
        if (s[j + 1] == s[i]) ++ j;
        fail[i] = j;
    }
    // 建失配树 + 倍增
    for (int i = 1; i <= n; ++ i) {
        fa[i][0] = fail[i];
        dep[i] = dep[fail[i]] + 1;
        for (int k = 1; k < LG; ++ k) fa[i][k] = fa[fa[i][k - 1]][k - 1];
    }
    while (m --) {
        int p, q; scanf("%d%d", &p, &q);
        int l = lca(p, q);
        if (l == p) l = fail[p];               // 排除自身
        else if (l == q) l = fail[q];
        printf("%d\n", l);
    }
    return 0;
}

复杂度：建树 O(n\log n)，每次询问 O(\log n)。

点评："border 链 = 树上的根路径"这个观察把字符串问题变成了树上问题，之后 LCA、倍增、树剖全部可用。这是失配树类题的统一入口。

操作四：DFS 序把"链上问题"变成"区间问题"

fail 链上的查询（"i 的祖先里有多少个满足某条件"）在树上是一次路径查询。若把所有询问离线，按 DFS 序处理，就能用树状数组把它变成区间加减 + 单点查询。

这是第 8 章 AC 自动机 P2414、P5840 的标准套路："某模式串在文本里出现几次" → "fail 树子树和" → "DFS 序 + 树状数组"。

4.11 应用：border 与周期

这一节的东西全是"沿 fail 链走"或"读 \pi 的值"，不需要 fail 树的额外结构。

求全部 border

定理：T[1..i] 的所有 border 长度，就是从 \text{fail}[i] 出发沿 fail 链走到的全部正整数。

这正是 §4.8 的引理，直接用：

// 枚举 T[1..n] 的全部 border 长度（降序）
for (int k = pi[n]; k; k = pi[k]) printf("%d ", k);

注意 pi[k] 还是 pi[k-1]：这取决于数组约定。若 pi[i] 存的是 \pi_i（1-indexed，下标即长度），下一步就是 pi[k]；若把 \pi_1..\pi_n 存在 pi[0..n-1]（0-indexed），下一步是 pi[k-1]。混用是最高频的错，写代码前先定死一种。

例题：P3375【模板】KMP

题意：给 s_1,s_2（长度 \le10^6，大写字母），输出 s_2 在 s_1 中所有出现位置，以及 s_2 每个前缀的最长 border 长度。

关键转化：这就是 3.6 的完整实现，直接套。

#include <bits/stdc++.h>
#define For(i, j, k) for (int i = j; i <= k; ++ i)
using namespace std;
const int N = 1e6 + 10;
int n, m, pi[N];
char s[N], t[N];
int main() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    pi[1] = 0;
    int j = 0;
    For(i, 2, m) {
        while (j && t[i] != t[j + 1]) j = pi[j];
        if (t[i] == t[j + 1]) ++ j;
        pi[i] = j;
    }
    j = 0;
    For(i, 1, n) {
        while (j && s[i] != t[j + 1]) j = pi[j];
        if (s[i] == t[j + 1]) ++ j;
        if (j == m) printf("%d\n", i - m + 1), j = pi[j];
    }
    For(i, 1, m) printf("%d ", pi[i]);
    return 0;
}

复杂度：O(n+m)。两段都是"j 单调攒、单调减"，总代价线性。

点评：这道题把 KMP 的两个用途（匹配 + 求前缀函数）合在一起，是最经济的模板。

最小循环节

定理：设 p=n-\pi_n。则

• 若 p\mid n：T 由长度 p 的串重复 n/p 次构成，p 是最小循环节长度；
• 若 p\nmid n：T 不是周期串，最小循环节长度为 n。

证明：由 border 与周期的等价，\pi_n 是 border 长度等价于 n-\pi_n=p 是周期。

先证 p\mid n 时是重复串：设 n=kp。由周期定义 T_i=T_{i+p} 对所有 i\le n-p 成立，把这串等式按模 p 分组，得 T_i=T_{i\bmod p}，即 T 由 T[1..p] 重复而成。

再证最小性：若存在更小的周期 q<p，则 n-q>\pi_n 也是 border 长度，与 \pi_n 最大矛盾。\square

int p = n - pi[n];
if (n % p == 0) printf("%d %d\n", p, n / p);   // 最小循环节长度、重复次数
else printf("%d 1\n", n);                       // 不是周期串

边界：n % p == 0 不能省。T=\texttt{aabaa}，n=5，\pi_5=2，p=3，5\nmid 3——直接输出 n/p=1 就错了。

例题：P4391 [BOI2009] Radio Transmission

题意：给一个字符串 s（|s|\le10^6），已知它是由某个串 t 自我连接若干次后再取一个前缀得到的（t 可以只出现一部分），求 t 的最短长度。

关键转化：这是"最小循环节"的弱化版——允许最后一个周期不完整。

观察：设 p=n-\pi_n。不论 n 是否被 p 整除，p 都是答案。

为什么：若 p\mid n，3.8 已证 p 是最小循环节。若 p\nmid n，设 n=kp+r（0<r<p），则 s 的前 kp 位由长度 p 的串重复构成，剩下 r 位正好是它的前缀——符合题意。而更小的周期会给出更长的 border，与 \pi_n 最大矛盾。

所以答案就是 n-\pi_n，不用判整除。这正是本题与 3.8 的区别：3.8 判"是否完整重复"，本题允许不完整。

#include <bits/stdc++.h>
#define For(i, j, k) for (int i = j; i <= k; ++ i)
using namespace std;
const int N = 1e6 + 10;
int n, pi[N];
char s[N];
int main() {
    scanf("%d%s", &n, s + 1);
    int j = 0;
    pi[1] = 0;
    For(i, 2, n) {
        while (j && s[i] != s[j + 1]) j = pi[j];
        if (s[i] == s[j + 1]) ++ j;
        pi[i] = j;
    }
    printf("%d\n", n - pi[n]);
    return 0;
}

复杂度：O(n)。

点评：一行答案 n - pi[n]。但要能说清"为什么不用判整除"——这是本题与普通最小循环节唯一的分歧点。

最大周期 = n- 最短 border

周期还有另一头：最短 border 给出最大周期。

定理：设 T[1..n] 的最短非空 border 长度为 b_{\min}，则最大周期长度为 n-b_{\min}。

证明：周期长度 q 与 border 长度 n-q 一一对应（周期定义即 T[1..n-q]=T[q+1..n]）。所以 q 最大 \iff n-q 最小，即 border 最短。\square

求最短 border：沿 fail 链走到不能再走（下一个是 0）。朴素走法是 O(n^2)，但可以用路径压缩：把每个点直接挂到它链底。

// 求每个前缀的最短非空 border（路径压缩，近似 O(n)）
For(i, 1, n) {
    int b = fail[i];
    if (b == 0) { mn[i] = 0; continue; }
    while (mn[b]) b = mn[b];       // 跳到链底
    mn[i] = b;                     // 记录：i 的最短 border 是 b
}

注意 mn[0] 恒为 0，所以循环终止条件是 mn[b] 非零而不是 b 非零——这个细节错了会死循环。

例题：P3435 [POI2006] OKR-Periods of Words

题意：给长度 k 的串（k\le10^6），求它所有前缀的"最大周期长度"之和。周期定义：Q 是 A 的真前缀且 A 是 QQ 的前缀。

关键转化：最大周期 = 前缀长度 − 最短 border 长度。

第一步：理解周期与 border 的对偶。

设 |A|=n，Q 是 A 的周期且 |Q|=q。则 A 是 QQ 的前缀，意味着 A[1..n] 与 A[q+1..q+n] 相同（在 QQ 里比较）。所以

即"长度为 n-q 的前缀等于同长度的后缀"——这正是 border 的定义。

第二步：等价关系。

验证：A=\texttt{ababab}，n=6。A 的 border 有 \texttt{abab}（长 4）、\texttt{ab}（长 2）。最短 border 是 \texttt{ab}（长 2），所以最大周期 =6-2=4，即 \texttt{abab} ✓（与题目说明一致）。

第三步：求最短 border。 沿 fail 链往上跳到最浅的非零节点（即 fail 链上除 0 外的最浅者）。但直接跳是 O(n^2)。

优化（路径压缩）：在求的过程中把 fail 数组"压缩"——若 fail[i] 的 fail 还能用，就让 fail[i] 直接指向那个更浅的。这样均摊 O(n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int fail[N];
int main() {
    int k; scanf("%d%s", &k, s + 1);
    for (int i = 2, j = 0; i <= k; ++ i) {
        while (j && s[j + 1] != s[i]) j = fail[j];
        if (s[j + 1] == s[i]) ++ j;
        fail[i] = j;
    }
    long long ans = 0;
    for (int i = 2; i <= k; ++ i) {
        int j = i;
        // 往上跳到最短的非零 border
        while (fail[j]) j = fail[j];
        if (fail[i]) fail[i] = j;        // 路径压缩
        ans += i - j;
    }
    printf("%lld\n", ans);
    return 0;
}

样例验证：babababa（k=8）输出 24 ✓。

复杂度：O(k)（路径压缩后均摊）。

点评："周期 \leftrightarrow border"的对偶是字符串里最重要的等价之一。它把"周期问题"全部转成"fail 链上的查询"。注意路径压缩那句 fail[i] = j——没有它复杂度退化到 O(n^2)。

本质不同子串数（副产品）

定理：长度 n 的串 T 的本质不同子串数为

证明（增量法）：逐个字符加入。加入第 i 个后，新增子串必然是"以 T_i 结尾"的那些，共 i 个候选。其中已经出现过的恰有 \pi_i 个：长度 1..\pi_i 的那些，因为 T[1..\pi_i]=T[i-\pi_i+1..i]，它们都是先前出现过的前缀。故净增 i-\pi_i，累加即得。\square

这只是理论上的公式：要真的数不同子串，O(n^2) 的这个做法没有实用价值，正解是后缀数组（§9）或 SAM（§10）。

4.12 应用：KMP 自动机

前面所有应用都是"边扫边跳 fail"。但如果要对同一段文本做很多次不同的匹配（或把匹配嵌进 DP），跳 fail 的均摊性就没了——每次都从头跳，最坏 O(nm)。

解法：把跳 fail 的过程预先算成转移表。

定义：状态 j\in[0,m] 表示"当前匹配了 T 的前 j 位"。对字符 c 定义转移

约定 \delta(0,c)=0 当 T_1\ne c。

这就是 KMP 自动机：m+1 个状态，|\Sigma| 条出边。有了它，匹配变成"读一个字符、走一条边"，严格 O(1)。

// nxt[j][c] = 当前匹配 j 位、读入字符 c 之后的状态
For(j, 0, m) For(c, 0, 25) {
    if (j < m && t[j + 1] == c + 'a') nxt[j][c] = j + 1;
    else if (j == 0)                   nxt[j][c] = 0;
    else                               nxt[j][c] = nxt[fail[j]][c];   // 查表，不再跳链
}

为什么是 O(m|\Sigma|)：nxt[fail[j]][c] 里的 fail[j] < j，所以按 j 递增的顺序算时它已经算好了，直接查表。跳 fail 被摊平进了预处理。

代价：空间 O(m|\Sigma|)。m=10^5 且 |\Sigma|=26 时是 2.6\times10^6 个 int，约 10 MB，可以接受；若 |\Sigma| 更大就要改用哈希表或按需建边。

三个典型用法：

第 8 章的 P3193 GT 考试就是第三种。注意这与第 8 章 AC 自动机的"禁串计数"是同一件事——那里把单串换成多串（Trie），矩阵规模从 m 变成 Trie 节点数。

例题：P4824 [USACO15FEB] Censoring S

题意：给串 S（|S|\le10^6）和模式串 T（|T|\le10^6），反复从 S 中删除 T 的第一次出现，直到 S 中不含 T。输出最终串。

关键转化：用栈模拟 + KMP 边扫边匹配。

朴素做法：每次删除后重新扫描——O(n^2)，会 TLE（n=10^6）。

关键观察：删除一段后，被删除部分左边的匹配状态不受影响。所以可以用栈保存"左边还没被删除的字符"，同时记录"每个栈位置对应的 KMP 匹配长度"。

做法：

1. 用栈 st 存字符，top[i] 存"处理到第 i 个栈元素时的 KMP 匹配长度"；
2. 每读一个字符，就推进 KMP；
3. 若匹配长度达到 |T|，说明栈顶的 |T| 个字符构成 T，弹出它们，并把 KMP 状态恢复成"弹出后的栈顶的匹配长度"。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N], t[N];
int fail[N], stk[N], top[N];
int main() {
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    // 求 T 的 fail
    for (int i = 2, j = 0; i <= m; ++ i) {
        while (j && t[j + 1] != t[i]) j = fail[j];
        if (t[j + 1] == t[i]) ++ j;
        fail[i] = j;
    }
    int tp = 0;
    for (int i = 1; i <= n; ++ i) {
        int j = top[tp];                       // 当前匹配长度 = 栈顶记录的
        while (j && t[j + 1] != s[i]) j = fail[j];
        if (t[j + 1] == s[i]) ++ j;
        stk[++ tp] = i;                        // 记录原串下标
        top[tp] = j;                           // 记录匹配长度
        if (j == m) tp -= m;                   // 匹配满，弹出 m 个
    }
    for (int i = 1; i <= tp; ++ i) putchar(s[stk[i]]);
    puts("");
    return 0;
}

复杂度：O(n+m)。

点评："栈 + 状态记录"是"反复删除"类问题的标准解法。关键是"恢复状态"——弹出后 KMP 状态自动回到 top[tp]，不需要重算。同类题还有 P3121 [USACO15FEB] Censoring G（多模式串，用 AC 自动机）。

例题：综合：CF1200E Compress Words

题意：给 n 个字符串（总长 \le10^6），按顺序合并：每次把新串接到当前答案后面，但重叠部分要合并（找最大的 k 使答案的后缀 k 位等于新串的前缀 k 位）。输出最终串。

第一步：问题化归

每次合并要求"最大重叠长度"——这正是Z 函数 / KMP 的 LCP 问题。设答案当前为 A，新串为 B，要求 \max k 使 A[|A|-k+1..|A|]=B[1..k]。

第二步：用 Z 函数求

构造 T=B+\texttt{\#}+A（# 是分隔符，防跨越），求 T 的 Z 函数。则对 A 的每个位置，z 值就是"从该位置起与 B 的 LCP"。我们只关心 A 的后缀部分，即取 T 中对应 A 起始位置之后的最大 z，且不超过 |B|。

更简单：只看 T 的最后一个位置开始往前……实际上只需取 \max_{i>|B|} \min(z_i,\ |B|)，但那不是"后缀"。

正确做法：要找的是"A 的某个后缀 = B 的前缀"，所以必须是 A 的末尾对齐。即 k 满足 A[|A|-k+1..|A|]=B[1..k]。用 T=B+\texttt{\#}+A，则 A 的末尾对应 T 的末尾，我们要的是"以 T 末尾为终点、长度 k 的串 = B 的前缀"。这不是 Z 直接给的（Z 给的是"从 i 开始向前匹配"）。

改用 KMP：求 B 的 \pi 数组，然后在 A 上跑匹配，最后停在 A 末尾时的 j 就是最大重叠长度。

// 求 A 的后缀与 B 的前缀的最大重叠长度
int max_overlap(const string &A, const string &B, const vector<int> &pi) {
    int j = 0, m = B.size();
    for (int i = max(0, (int)A.size() - m); i < (int)A.size(); ++ i) {
        while (j && A[i] != B[j]) j = pi[j - 1];
        if (A[i] == B[j]) ++ j;
        if (j == m) { if (i != (int)A.size() - 1) j = pi[j - 1]; }   // 完整匹配但没到末尾
    }
    return j;
}

第三步：总复杂度

每次只在 A 的最后 \min(|A|,|B|) 位上跑，总长度受限于 \sum|B_i|，所以总 O(\sum|s_i|)。

点评：这道题说明一个常见模式——"求最大重叠"就是"跑 KMP 停在末尾时的 j"。它比"求 LCP"更具体，因为对齐全在末尾。同时也提醒：用 Z 函数时会因为"要从末尾对齐"而绕远路，KMP 在这里更直接。

习题池：KMP / 失配树 / 周期

入门·普及

提高

省选

NOI

4.13 本章小结：一棵 fail 树，四副面孔

KMP 的全部内容可以压缩成两句话：

1. \pi_i（= \text{fail}[i]）是"最长相等前后缀"，而所有 border 构成一条沿 fail 递减的链；
2. 把 fail 当父亲，链就长成一棵树——于是链上的问题全变成树上的标准问题。

本章的五个应用，全部归到这两句话：

为什么要在这里把 fail 树讲透

因为第二部分的三个自动机都是它的推广。同样是"把指针当父亲建树"，同样是"子树和 = 出现次数"：

四棵树的节点含义不同，但形状和用法完全一致。所以这一章的 fail 树不是"KMP 的一个应用"，而是后面三个自动机的样板：

• 想知道"某模式串出现了几次" → 找它的 fail 树，求子树和；
• 想知道"两个串的最长公共后缀/边界" → 找 LCA；
• 想统计"有多少个状态满足某条件" → DFS 序 + 树状数组。

第 8 章讲 AC 自动机时，只需要说一句"把单串换成 Trie，fail 的定义从'最长 border'改成'最长的、且是某模式串前缀的真后缀'"，其余全部沿用本章。

三个容易混的点

① \pi_i 的下标是"长度"，不是"位置"。 \pi_{\pi_i} 这种写法里，内层 \pi_i 是一个长度，外层拿它当下标。数组实现时若用 0-indexed，一律要减 1。这是本章最容易出错的地方。

② 失配跳的是 j，不是 i。 朴素算法让起点右移（i 回退），KMP 让匹配长度缩短（j 跳 fail），而 i 单调不减。O(n) 的全部来源就在这一句。

③ 匹配成功后要 j = fail[j]。 清零会漏掉重叠出现（aa 在 aaaa 中出现在 1、2、3）。

5. Z 函数与扩展 KMP

5.1 它回答什么问题

KMP 的前缀函数 \pi_i 回答"s[0..i] 的最长 border"——它关心前缀。但有一类问题问的是后缀：

对每个位置 i，求 s[i..n-1] 与整个 s 的最长公共前缀（LCP）长度。

定理：Z 函数可以在 O(n) 时间内算出。

证明：只看 while 循环的总执行次数。

先看它什么时候会成功执行。设这次成功让 z_i 从 v 变成 v+1。由于 z[i] 的初值满足 v\ge\max(0,r-i+1)，且此时在比较 s[v] 与 s[i+v]——

• 若 v>r-i，即 i+v>r：这一位的比较发生在 r 之外，比较完后 i+z[i]-1=i+v>r，后面必然触发线段更新，r 被推到 i+v。即 r 至少增加 1。
• 若 v\le r-i：这会与初值 v\ge\max(0,r-i+1) 矛盾（当 i\le r 时初值是 r-i+1，而 v 是在初值基础上累加的，所以第一次成功执行时必然 v=r-i+1>r-i）。

所以：每一次 while 成功，都把 r 至少推进 1。

证明要点：r 单调不减，且每次成功扩展都把它推进至少一格；推进量被上界 n 卡住。

这个论证与 KMP 的 O(n) 论证是同一个模式（4.5 节）：某个量单调移动、每次移动都有代价、总移动量有上界。Z 函数推的是 r，KMP 推的是 j，单调队列推的是队尾指针。

5.11 扩展 KMP：两个串的版本

问题：给定文本串 S（长 n）与模式串 T（长 m），求每个 i 的

即"从 S 的第 i 位开始，能与 T 匹配多长"。

结构完全一样，只是"参照串"和"被扫描串"分开了：

• 线段 [l,r] 的含义变成 S[l..r]=T[0..r-l]；
• 位置 i 对应 T 的 k=i-l，查的仍是 T 的 z_k；
• 匹配不能超过 T 的长度 m。

// 扩展 KMP：p[i] = LCP(T, S[i..])，0-indexed
vector<int> exkmp(const string &S, const string &T) {
    int n = S.size(), m = T.size();
    if (m == 0) return vector<int>(n, 0);
    vector<int> z = z_function(T);          // 先算 T 自己的 Z
    vector<int> p(n, 0);
    for (int i = 0, l = 0, r = -1; i < n; ++ i) {
        if (i <= r && z[i - l] < r - i + 1)
            p[i] = z[i - l];                // 情形一：抄 T 的镜像
        else
            p[i] = max(0, r - i + 1);       // 情形二：只抄到边界
        while (i + p[i] < n && p[i] < m && S[i + p[i]] == T[p[i]])
            ++ p[i];                        // 注意 p[i] < m 上界
        if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
    return p;
}

与单串 Z 的差别：

p[i] < m 这一条最容易漏。漏了会读到 T[m] 之后；若内存里恰好是某个能与 S 匹配的字节，答案会偏大。

为什么 r 初始为 -1：单串的 z_0=0 意味着位置 0 没有匹配段，r=0 只是一个占位。两串版本 p_0 需要真算，所以置 r=-1 表示"还没有任何线段"。

m == 0 的判空：T 为空时 z 数组为空，z[i-l] 会越界。

复杂度：O(n+m)，论证同 5.10。

与 KMP 的分工：

相关例题　P5410 【模板】扩展 KMP（Z 函数） · P8112 符文破译

例题：P5410【模板】扩展 KMP（Z 函数）

题意：给串 a,b（|a|,|b|\le2\times10^7），求 b 与 a 的每个后缀的 LCP（ext_i），以及 b 自己的 z 数组。

关键转化：参照串换成 b，被扫描串换成 a，其余不变。

// 1-indexed 版本（洛谷模板题用这套约定）
void exkmp(char *a, int n, char *b, int m, int *z, int *ext) {
    z[1] = m;
    for (int i = 2, l = 0, r = 0; i <= m; ++ i) {
        if (i <= r && z[i - l + 1] < r - i + 1) z[i] = z[i - l + 1];
        else z[i] = max(0, r - i + 1);
        while (i + z[i] <= m && b[z[i] + 1] == b[i + z[i]]) ++ z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    for (int i = 1, l = 0, r = 0; i <= n; ++ i) {
        if (i <= r && z[i - l + 1] < r - i + 1) ext[i] = z[i - l + 1];
        else ext[i] = max(0, r - i + 1);
        while (i + ext[i] <= n && ext[i] < m && b[ext[i] + 1] == a[i + ext[i]]) ++ ext[i];
        if (i + ext[i] - 1 > r) l = i, r = i + ext[i] - 1;
    }
}

复杂度：O(n+m)。

三个 1-indexed 的坑：

1. 镜像下标是 z[i - l + 1] 而不是 z[i - l]（下标整体加一）。
2. z[1] = m（1-indexed 的"自己与自己"）。
3. 第二段 while 必须有 ext[i] < m。

验证：a=\texttt{aabaabaaa}，b=\texttt{aabaa}，得 ext=[5,1,0,5,1,0,2,2,1]，与暴力 LCP 一致。

5.12 与 KMP 的互相转化

定理：给定 z 数组可以 O(n) 求出 \pi 数组。

思路：z_i=k（k>0）意味着"s[i..i+k-1]=s[0..k-1]"，即位置 i+k-1 处存在一个长度 k 的 border。把每条信息记到右端点，再从右往左传递。

// 由 z 求 pi（0-indexed，pi[i] = s[0..i] 的最长 border 长度）
vector<int> z2pi(const vector<int> &z) {
    int n = z.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++ i)
        if (z[i]) pi[i + z[i] - 1] = max(pi[i + z[i] - 1], z[i]);
    for (int i = n - 2; i >= 0; -- i)
        pi[i] = max(pi[i], pi[i + 1] - 1);
    return pi;
}

为什么第二条循环是 pi[i+1]-1：若 s[0..i+1] 有长度 L 的 border，两边各砍末位，得 s[0..i] 有长度 L-1 的 border。所以左邻能继承"右邻减一"。

验证：s=\texttt{aabaabaaa}，z=[0,1,0,5,1,0,2,2,1]，算得 \pi=[0,1,0,1,2,3,4,5,2]，与直接求一致。

反方向（\pi\to z）通常不做，直接跑 Z 算法更省事。

5.13 三个应用

应用一：一次求出所有位置的匹配长度。 T 在 i 出现 \iff p_i=m。并顺带得到所有"部分匹配"长度，这是 KMP 给不了的。

应用二：字符串整周期。 若存在 k 使 z_k=n-k，且 k 是使该式成立的最小正数，则 s 由长度 k 的串重复而成。

应用三：比较两个后缀的大小。 求出 \operatorname{lcp}(s[i..],s[j..])=L 后，比较 s[i+L] 与 s[j+L] 即可定序。这是后缀数组倍增法的基础（9.2 节）。

相关例题　P5546 [POI2000] 公共串 · P8112 符文破译

5.14 本章小结

Z 函数只有一句话：维护一条右端点最靠右的匹配段 [l,r]，段内的位置直接抄镜像的答案，抄到线段边界再自己往外比。

拆成四条：

1. 匹配段：z_i=k 产生区间 [i,i+k-1]，段内 s[i..i+k-1]=s[0..k-1]（5.3）。
2. 对齐：[l,r] 使 s[i..r]=s[i-l..r-l]，所以 i 与 k=i-l 行为相同（5.4）。
3. 边界：等式只在 [l,r] 内成立，所以初值取 \min(z_k,\ r-i+1)（5.5）。
4. 推进：i+z_i-1>r 就更新线段；r 单调不减是 O(n) 的唯一依据（5.7、5.10）。

三个最容易犯的错：

• 忘了 r-i+1 这个上界，直接 z[i] = z[i-l]，在情形二越界。
• z[0] 的约定混用（0 或 n），涉及位置 0 时答案错。
• 扩展 KMP 漏了 p[i] < m 上界，读到模式串之外。

与 KMP 的关系：同一套"单调推进量"论证（KMP 推 j，Z 推 r），同一份"前后缀重合"信息（5.12 给了确切转化）。

习题池：Z 函数与扩展 KMP

6. Manacher

6.1 动机：回文的两条对称

回文指正读反读相同的串，如 abba、aba。

朴素求最长回文子串：枚举中心，向两边扩，O(n^2)。n=10^7 时这是 10^{14}，完全不可行。

关键观察：回文有极强的对称性。若已知 [l,r] 是回文，那么对其中任意点 i，它的镜像点 j=l+r-i 处的回文半径与 i 处"应该有关"。这正是 Manacher 的全部思想——和 Z 函数的"最右匹配段"是同一个套路，只是把"前缀相等"换成了"镜像相等"。

6.2 奇偶统一

回文分奇长度（aba，中心是一个字符）和偶长度（abba，中心在两个字符之间）。分两种讨论会写两套代码。

统一办法：在每两个字符之间插入一个分隔符，首尾也加。例如 s=\texttt{abba} 变成 \#\texttt{a}\#\texttt{b}\#\texttt{b}\#\texttt{a}\#（长度 2n+1）。

这样所有回文都变成奇数长度，且原串的每种回文都对应新串里以某个 # 或字符为中心的奇数长回文。求完后 \text{原长}=\lfloor\text{新半径}\rfloor（具体换算见 5.5）。

注意事项：分隔符必须不出现在原字符集中（用 #、|、或 0 这类哨兵）。若原串含所有可打印字符，就用整数数组。

6.3 算法

记 d_i 为以 i 为中心、向外能扩多少位（不含中心）。维护当前"右端点最靠右的回文" [l,r]。

情形一：i>r。暴力扩。

情形二：i\le r。设 j=l+r-i 是 i 关于中心的对称点。则 d_i 至少是 \min(d_j,\ r-i)：

• 若 d_j<r-i：d_i=d_j（镜像是完整的）；
• 否则 d_i\ge r-i，从 r+1 继续暴力扩。

// Manacher（返回的是插入分隔符后的半径数组）
vector<int> manacher(const string &s) {
    string t = "#";
    for (char c : s) t += c, t += '#';
    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = -1; i < n; ++ i) {
        int k = (i > r) ? 0 : min(d[l + r - i], r - i);
        while (i - k - 1 >= 0 && i + k + 1 < n && t[i - k - 1] == t[i + k + 1]) ++ k;
        d[i] = k;
        if (i + k > r) l = i - k, r = i + k;
    }
    return d;
}

min(d[l + r - i], r - i) 的来源：l+r-i 是镜像点，d[l+r-i] 是镜像的半径，r-i 是"到已知右边界的距离"。取小值，理由和 Z 函数完全一致。

相关例题　P3805 【模板】manacher · CSES-1111 Longest Palindrome

Manacher：插入分隔符后统一奇偶，镜像复用半径

例题：P3805【模板】Manacher

题意：给只含小写字母的串（n\le1.1\times10^7），求最长回文子串长度。

关键转化：n=1.1\times10^7，必须是 O(n) 且常数小。Manacher + 插入分隔符。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e7 + 10;
char s[N], t[N];
int d[N];
int main() {
    scanf("%s", s);
    int n = strlen(s), m = 0;
    t[m ++] = '#';                                  // 奇数位置放 '#'
    for (int i = 0; i < n; ++ i) t[m ++] = s[i], t[m ++] = '#';
    int ans = 0;
    for (int i = 0, l = 0, r = -1; i < m; ++ i) {
        int k = (i > r) ? 0 : min(d[l + r - i], r - i);
        while (i - k - 1 >= 0 && i + k + 1 < m && t[i - k - 1] == t[i + k + 1]) ++ k;
        d[i] = k;
        if (i + k > r) l = i - k, r = i + k;
        ans = max(ans, k);                          // 插入分隔符后最长回文长 = max d
    }
    printf("%d\n", ans);
    return 0;
}

关于 ans = max(ans, k)：插入分隔符后，以某中心、半径 k 的回文长度为 2k+1，其中原串字符有 k 个、分隔符 k+1 个。所以原串对应的回文长度恰好是 k。这就是为什么答案直接是 \max d。

验证：s=\texttt{aaa}，t=\texttt{\#a\#a\#a\#}。中心 i=2（第二个 a）时 k=3，答案 3 ✓。

复杂度：O(n)，空间 O(n)。n=1.1\times10^7 时 d 数组要开 2.2\times10^7 个 int，约 88 MB——必须开全局且用 int 不用 long long。

点评：这道题的记忆点是"插入分隔符后答案是 \max d"，很多人记成 \max(2d+1) 就错了。

6.4 复杂度

定理：Manacher 是 O(n)。

证明：与 Z 函数同理——r 单调不减，while 每次成功都推进 r，总推进量 O(n)。\square

6.5 从半径还原原串信息

插入分隔符后，d_i 是"向外扩展的步数"。设原串长度为 n，新串长度 2n+1。

• 若 i 处是分隔符 #（i 为奇数，0-indexed）：对应偶长度回文，原长为 2d_i；
• 若 i 处是字符（i 为偶数）：对应奇长度回文，原长为 2d_i+1。

最长回文子串长度 =\max_i(2d_i+1) 的一半取整……更稳妥的写法是直接用原长公式：

// 最长回文子串长度
int ans = 0;
For(i, 0, (int)d.size() - 1) {
    int len = (i & 1) ? 2 * d[i] : 2 * d[i] + 1;   // 奇数下标是 '#'，对应偶数长度
    ans = max(ans, len);
}

更简单的记法：插入分隔符后，最长回文子串的长度恰好等于 \max_i d_i（因为分隔符版本的回文长度是 2d_i+1，而原串对应长度是 d_i……两种记法差一个常数）。考场上的做法是手算小例子核对一遍，不要凭记忆。

6.6 应用：回文串计数

应用一：回文串总数。以每个中心为心的回文个数：若 d_i 是半径，则以该中心为中心的回文串有 d_i+1 个（半径 0..d_i 各一个）。但不同中心可能对应同一个回文串吗？不会——一个回文串的中心唯一。所以总数 =\sum_i(d_i+1)。

应用二：本质不同的回文子串数。必须用 PAM（第二卷），Manacher 做不到。

应用三：回文划分。把 s 划分成若干个回文串，方案数。需要 PAM 的 fail 链 DP（第二卷）。

相关例题　P1659 拉拉队排练 · P4555 最长双回文串 · P4287 双倍回文

例题：P4287 [SHOI2011] 双倍回文

题意：若一个回文串可以写成 ww^Rww^R 的形式（w^R 是 w 的反转），称它为双倍回文。给 s（|s|\le5\times10^5），求最长双倍回文子串的长度。

第一步：理解结构

证明要点：把"p_v 是 p_u 的后缀"翻译成 fail 树上的祖先关系，子树求和即可。

实现：按 BFS 逆序（深度从深到浅）做 cnt[fail[u]] += cnt[u]。

// 文本串跑完后，按 BFS 逆序累加
for (int i = tot; i >= 1; -- i)          // 按节点编号逆序（BFS 序保证父亲编号 < 儿子）
    cnt[fail[i]] += cnt[i];

为什么逆序就够：BFS 建 fail 时，父亲的编号一定小于儿子的编号（Trie 是先序建、BFS 是层序算 fail，但 ch 数组的编号是插入顺序，不一定满足）。更稳的做法是记录 BFS 序列，然后倒序遍历。

int qq[N], qh;                           // BFS 序
// build() 里：qq[++ qh] = v;
// 逆序累加
for (int i = qh; i >= 1; -- i) {
    int u = qq[i];
    cnt[fail[u]] += cnt[u];
}

例题：P5357 【模板】AC 自动机（二次加强版）

题意：同 12.1，但要输出每个模式串的出现次数。|T|\le2\times10^6。

关键转化：fail 树子树求和（第 1.5 节）。

为什么 12.1 的做法不行：12.1 用 vis 去重，但本题要精确次数，不能去重。而暴力沿 fail 链跳的总复杂度是 O(|T|\cdot\text{链长})，会 TLE。

做法：文本串跑完后，只给"到达的状态"计数，然后按 BFS 逆序做 cnt[fail[u]] += cnt[u]。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int ch[N][26], fail[N], tot = 1;
int ed[N], cnt[N];
int qq[N], qh;                            // BFS 序

void insert(const char *s, int id) {
    int u = 1;
    for (int i = 0; s[i]; ++ i) {
        int c = s[i] - 'a';
        if (!ch[u][c]) ch[u][c] = ++ tot;
        u = ch[u][c];
    }
    ed[u] = id;
}
void build() {
    queue<int> q;
    for (int c = 0; c < 26; ++ c)
        if (ch[1][c]) fail[ch[1][c]] = 1, q.push(ch[1][c]);
        else ch[1][c] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        qq[++ qh] = u;                     // 记录 BFS 序
        for (int c = 0; c < 26; ++ c) {
            int v = ch[u][c];
            if (v) fail[v] = ch[fail[u]][c], q.push(v);
            else ch[u][c] = ch[fail[u]][c];
        }
    }
}
int main() {
    int n; scanf("%d", &n);
    static char s[N * 10];
    for (int i = 1; i <= n; ++ i) scanf("%s", s), insert(s, i);
    build();
    scanf("%s", s);
    int u = 1;
    for (int i = 0; s[i]; ++ i) {
        u = ch[u][s[i] - 'a'];
        ++ cnt[u];                          // 只给到达的状态计数
    }
    for (int i = qh; i >= 1; -- i) {        // BFS 逆序累加
        int v = qq[i];
        cnt[fail[v]] += cnt[v];
    }
    // 输出：每个模式串的节点 ed 对应的 cnt
    return 0;
}

复杂度：O(\sum|s_i|\cdot26+|T|)，不再有 fail 链的额外开销。

点评："只计数到达的状态 + BFS 逆序累加"是 AC 自动机统计的标准做法。它把"沿链跳"变成"一次树形累加"。

8.6 AC 自动机上的 DP

模型：在 AC 自动机上走 n 步，每步选一个字符，统计路径数（可能带"不能经过某些节点"的限制）。

状态：(u,\text{步数})，u 是 AC 自动机的状态。

转移：f_{k+1}[ch[u][c]]\mathrel{+}=f_k[u]。

"不能经过"的处理：若某节点 u 代表一个模式串的结尾，或它的 fail 链上某个节点是模式串结尾，则 u 是"禁止节点"。在建 fail 时标记：

// build() 中
if (v) {
    fail[v] = ch[fail[u]][c];
    bad[v] |= bad[fail[v]];              // 关键：继承 fail 的禁止标记
    q.push(v);
}

为什么必须继承：因为"p_u 的某个后缀是模式串"意味着"走到 u 时，那个模式串已经完整出现了"。

相关例题　P4052 [JSOI2007] 文本生成器 · P3311 [SDOI2014] 数数 · P2444 [POI2000] 病毒

例题：P4052 [JSOI2007] 文本生成器

题意：给 n 个模式串（总长 \le6000），求有多少个长度为 m（m\le100）的字符串至少包含一个模式串，模 10^4+7。

关键转化：补集 + AC 自动机上 DP（正难则反）。

第一步：反向计数。 "至少包含一个"的补集是"一个都不含"。所以

第二步：拆成"禁止节点"。 AC 自动机上，若状态 u 是某模式串的结尾，或 u 的 fail 链上有模式串结尾，则 u 是禁止节点（走到它就说明某个模式串已经完整出现）。

关键是建 fail 时继承禁止标记：

bad[v] |= bad[fail[v]];      // ★ 在 build() 的 BFS 里，这一步不能漏

第三步：在 AC 自动机上 DP。 设 f(k,u) 为"走了 k 步、当前在状态 u、全程没经过禁止节点"的方案数。转移：

答案就是 26^m-\sum_{u}f(m,u)。

#include <bits/stdc++.h>
using namespace std;
const int N = 6010, MOD = 10007;
int ch[N][26], fail[N], tot = 1;
bool bad[N];
int f[2][N];

void insert(const char *s) {
    int u = 1;
    for (int i = 0; s[i]; ++ i) {
        int c = s[i] - 'A';
        if (!ch[u][c]) ch[u][c] = ++ tot;
        u = ch[u][c];
    }
    bad[u] = true;
}
void build() {
    queue<int> q;
    for (int c = 0; c < 26; ++ c)
        if (ch[1][c]) fail[ch[1][c]] = 1, q.push(ch[1][c]);
        else ch[1][c] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        bad[u] |= bad[fail[u]];                 // ★ 继承禁止标记
        for (int c = 0; c < 26; ++ c) {
            int v = ch[u][c];
            if (v) fail[v] = ch[fail[u]][c], q.push(v);
            else ch[u][c] = ch[fail[u]][c];
        }
    }
}
int main() {
    int n, m; scanf("%d%d", &n, &m);
    char s[110];
    for (int i = 1; i <= n; ++ i) scanf("%s", s), insert(s);
    build();
    f[0][1] = 1;                                // 从根出发
    for (int k = 0; k < m; ++ k) {
        memset(f[(k + 1) & 1], 0, sizeof f[0]);
        for (int u = 1; u <= tot; ++ u) {
            if (!f[k & 1][u] || bad[u]) continue;
            for (int c = 0; c < 26; ++ c) {
                int v = ch[u][c];
                if (bad[v]) continue;           // 不进入禁止节点
                f[(k + 1) & 1][v] = (f[(k + 1) & 1][v] + f[k & 1][u]) % MOD;
            }
        }
    }
    int sum = 0;
    for (int u = 1; u <= tot; ++ u) if (!bad[u]) sum = (sum + f[m & 1][u]) % MOD;
    // 答案 = 26^m - sum
    int all = 1;
    for (int i = 1; i <= m; ++ i) all = all * 26 % MOD;
    printf("%d\n", (all - sum + MOD) % MOD);
    return 0;
}

复杂度：O(m\cdot\text{节点数}\cdot26)。节点 6000、m=100 时约 1.6\times10^7。

要点：bad[u] |= bad[fail[u]] 是本题唯一的核心——它保证"走到 u 就意味着某个模式串已经出现"。漏了这句，只有"以模式串结尾"的节点被禁，而"u 的后缀是模式串"的情况全部漏判。

8.7 复杂度与实现陷阱

陷阱一：fail[root] 的值。 根的 fail 应设为 0（或根自己），且根的儿子的 fail 必须是根。写成根的儿子 fail 为 0 会导致死循环。

陷阱二：多组数据不清空。 tot 重置为 1，且清空 ch[1] 那一行。

陷阱三：忘记继承禁止标记。 见 1.6。

陷阱四：统计出现次数时用节点编号逆序。 必须用 BFS 序逆序，不是编号逆序（两者可能不一致）。

8.8 延伸阅读（更多同知识点题目）

相关例题　P3808 【模板】AC 自动机（简单版） · P3796 【模板】AC 自动机（简单版 II） · P5357 【模板】AC 自动机（二次加强版） · P2444 [POI2000] 病毒 · P2414 [NOI2011] 阿狸的打字机 · P4052 [JSOI2007] 文本生成器 · P3311 [SDOI2014] 数数 · P5840 [COCI2015] Divljak · P3121 [USACO15FEB] Censoring G · CF1437G Death DBMS

习题池：AC 自动机 / 多模式匹配

提高

省选·NOI

8.9 这一节要带走的三句话

1. fail 指向"最长真后缀且是某模式串前缀"的节点，BFS 建，靠 fail[fa]\to c 递推。
2. Trie 图把缺失边补全，匹配时 O(1) 转移，代价是空间 \times|\Sigma|。
3. fail 树上的子树求和 = 出现次数，这是 AC 自动机最重要的性质。

9. 后缀数组

9.1 它解决什么问题

核心洞察（0.1 节已经点出）：

所以把 n 个后缀按字典序排好序，所有"子串"问题就变成了"有序数组上的区间问题"。

后缀数组就是"排好序的后缀"：

两者互逆：sa[rank[i]]=i，rank[sa[i]]=i。

关键副产品：height 数组。

为什么 height 重要：因为任意两个后缀的 LCP 就等于它们排名区间上 height 的最小值：

于是 LCP 查询变成 RMQ，O(1) 回答（配合 ST 表）。

9.2 倍增构造

后缀数组：排序后的后缀与 height（橙色为相邻 LCP） 朴素做法：把所有后缀取出来排序，比较两个后缀是 O(n)，总 O(n^2\log n)。

倍增思路：用"长度为 2^k 的前缀的排名"推"长度为 2^{k+1} 的排名"。

设 rk_k[i] 为"从 i 开始长度 2^k 的子串"的排名。则长度为 2^{k+1} 的子串可以拆成两半：

所以比较两个长为 2^{k+1} 的子串，只需比较二元组

这就把"字符串比较"变成了"二元组比较"，可以用基数排序 O(n) 完成一轮。

轮数：\lceil\log_2 n\rceil 轮。总复杂度 O(n\log n)。

终止条件：当所有 rk_k 互不相同（或者说 rk_k 的最大值 =n）时，说明后缀已经完全区分开了，可以停。

9.3 倍增正确性

定理 2.1：倍增法第 k 轮结束后，rk_k[i]<rk_k[j] 当且仅当"从 i 开始长 2^k 的子串"字典序小于"从 j 开始的"。

证明（对 k 归纳）：

k=0：rk_0[i] 就是 s_i 的大小关系，直接按字符排序得到 ✓。

归纳步：设对 k 成立。长度为 2^{k+1} 的子串 A=s[i..i+2^{k+1}-1] 与 B=s[j..j+2^{k+1}-1] 比较字典序，先比前 2^k 个字符，若不同则由归纳假设等价于比 rk_k[i] 与 rk_k[j]；若相同，则比后 2^k 个字符，等价于比 rk_k[i+2^k] 与 rk_k[j+2^k]。

所以字典序比较等价于二元组 (rk_k[i],rk_k[i+2^k]) 的字典序比较。按二元组基数排序即得 rk_{k+1} ✓。\square

证明要点：2^{k+1} 长的串拆成两个 2^k 长的串，字典序比较恰好是二元组比较。

注意"越界"的处理：当 i+2^k>n 时，后半部分视为"空"，排名最小（0）。

9.4 实现

const int N = 1e6 + 10;
int sa[N], rk[N << 1], oldrk[N << 1], cnt[N], id[N];
char s[N];
int n, m;                          // m = max(n, 字符集大小)

bool cmp(int i, int j, int w) {    // 比较 (rk[i], rk[i+w]) 与 (rk[j], rk[j+w])
    if (oldrk[i] != oldrk[j]) return oldrk[i] < oldrk[j];
    return oldrk[i + w] < oldrk[j + w];
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    m = max(n, 300);
    // 第一轮：按字符排序
    for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = s[i]];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
    // 倍增
    for (int w = 1; w < n; w <<= 1) {
        memcpy(oldrk, rk, sizeof(int) * (n + w + 1));   // ★ 必须开 2n 并清零
        int p = 0;
        for (int i = n; i > n - w; -- i) id[++ p] = i;  // 后半段为空的，排最前
        for (int i = 1; i <= n; ++ i)
            if (sa[i] > w) id[++ p] = sa[i] - w;
        memset(cnt, 0, sizeof(int) * (m + 1));
        for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i]]];
        for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i]]] --] = id[i];
        // 重算 rk
        p = 0;
        for (int i = 1; i <= n; ++ i) {
            if (i == 1 || cmp(sa[i], sa[i - 1], w)) ++ p;
            rk[sa[i]] = p;
        }
        if (p == n) break;                              // 已全部区分
        m = p;
    }
    for (int i = 1; i <= n; ++ i) printf("%d ", sa[i]);
    return 0;
}

两个必错的坑：

1. oldrk 要开 2n 并清零。因为 oldrk[i+w] 在 i+w>n 时会被访问，越界位必须是 0（表示"空后缀最小"）。
2. memcpy 的长度要含 w：sizeof(int) * (n + w + 1)，否则 oldrk[n+1..n+w] 是垃圾值。

例题：P3809 【模板】后缀排序

题意：给串 s（|s|\le10^6），输出它的后缀数组 sa[1..n]。

关键转化：倍增 + 基数排序（第 2.2、2.4 节）。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int sa[N], rk[N << 1], oldrk[N << 1], cnt[N], id[N];
char s[N];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = max(n, 300);
    for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = s[i]];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
    for (int w = 1; w < n; w <<= 1) {
        memcpy(oldrk, rk, sizeof(int) * (n + w + 1));     // ★ 含 w
        int p = 0;
        for (int i = n; i > n - w; -- i) id[++ p] = i;
        for (int i = 1; i <= n; ++ i) if (sa[i] > w) id[++ p] = sa[i] - w;
        memset(cnt, 0, sizeof(int) * (m + 1));
        for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i]]];
        for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i]]] --] = id[i];
        p = 0;
        auto cmp = [&](int x, int y) {
            if (oldrk[x] != oldrk[y]) return oldrk[x] < oldrk[y];
            return oldrk[x + w] < oldrk[y + w];
        };
        for (int i = 1; i <= n; ++ i) {
            if (i == 1 || cmp(sa[i - 1], sa[i])) ++ p;   // ★ 注意实参顺序
            rk[sa[i]] = p;
        }
        if (p == n) break;                                // 提前退出
        m = p;
    }
    for (int i = 1; i <= n; ++ i) printf("%d ", sa[i]);
    return 0;
}

复杂度：O(n\log n)。

点评：三个坑——oldrk 开 2n 并清零、memcpy 长度含 w、提前退出。漏任何一个都会 WA 或 RE。

9.5 O(n) 求 height

朴素求 height：对每个 i，与 sa[rank[i]-1] 暴力比较，O(n^2)。

关键性质：

其中 h[i]=height[rank[i]]=\operatorname{lcp}(i,\ sa[rank[i]-1])。

证明：设 h[i-1]=L，即后缀 i-1 与它的前一名 j=sa[rank[i-1]-1] 的 LCP 是 L。

考虑后缀 i 与 j+1：

• 因为后缀 i-1 与 j 的前 L 个字符相同，所以去掉首字符后，后缀 i 与 j+1 的前 L-1 个字符相同（若 L\ge1）。
• 所以 \operatorname{lcp}(i,j+1)\ge L-1。
• 现在 rank[i] 与 rank[j+1] 的关系：因为 rank[j+1] 可能不等于 rank[i]-1，但 j+1 与 i 之间的后缀（在排名上）与 i 的 LCP 都 \ge \operatorname{lcp}(i,j+1)（由 LCP 的单调性，见 (5)：区间最小值）。
• 所以 h[i]=\operatorname{lcp}(i,sa[rank[i]-1])\ge\operatorname{lcp}(i,j+1)\ge L-1=h[i-1]-1。\square

证明要点：把"后缀 i-1 与 j 的 LCP"削掉首字符，得到"后缀 i 与 j+1 的 LCP 至少 L-1"，再用 LCP 的区间最小值性质传递到"相邻排名"。

由这条性质，求 height 可以"只往右试，不回退"：

// O(n) 求 height，h[i] = height[rank[i]]
for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) { k = 0; continue; }       // 排名第一，没有前一名
    if (k) -- k;                                // 利用 h[i] >= h[i-1]-1
    int j = sa[rk[i] - 1];
    while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++ k;
    height[rk[i]] = k;
}

复杂度：O(n)。理由：k 每次循环最多加 1（while 里），而每轮开头 --k 最多减 1，所以 k 的总增量 \le 2n。

9.6 五个经典应用

应用一：本质不同子串数

为什么：按排名顺序处理后缀。处理第 i 个后缀时，它贡献了 n-sa[i]+1 个前缀（子串），其中与前一名重复的恰好有 height[i] 个（因为前 height[i] 个字符构成的前缀已经在前面出现过）。\square

注意：为什么"与前一名重复"就够，不需要考虑所有前面的后缀？因为 LCP 的区间最小值性质——与任意更早后缀的 LCP 都不超过与前一名的 LCP。

应用二：最长公共子串（两串）

把两串拼起来（中间加分隔符），求 SA 与 height。答案是"height 中满足 sa[i-1] 与 sa[i] 分属两个串的最大值"。

应用三：最长公共子串（多串）

拼接后二分答案 L，检查"是否存在长度 L 的 height 段覆盖所有串"。用单调队列或双指针。

应用四：出现至少 k 次的最长子串

二分答案 L，检查"height 中是否存在长度 \ge k-1 的连续段，其中每个值都 \ge L"。

应用五：任意两后缀的 LCP

用 (5) + ST 表，O(1) 回答。

例题：P2408 不同子串个数

题意：给串 s（|s|\le10^5），求本质不同子串个数。

关键转化：SA + height（第 2.6 节应用一）。

// 求出 sa 与 height 后
long long ans = 0;
for (int i = 1; i <= n; ++ i)
    ans += (n - sa[i] + 1) - height[i];
printf("%lld\n", ans);

复杂度：O(n\log n)（求 SA）或 O(n\log n)（求 height 是 O(n)）。

另一解法（SAM）：\sum_{u\ne root}(len[u]-len[link[u]])，O(n)。建议用 SAM——更快更短。

点评：这道题是"SA 与 SAM 都能做、而 SAM 更优"的典型。它揭示了两者的本质关系：(9) 式的 SAM 公式与 (7) 式的 SA 公式完全等价。

例题：P2178 [NOI2015] 品酒大会

题意：给串 s（|s|\le3\times10^5）和权值 a_i。对每个 r=0..n-1，求：

• 有多少对 (i,j)（i<j）满足"从 i,j 开始的后缀的 LCP \ge r"；
• 这些对中 a_i\cdot a_j 的最大值。

关键转化：SA + 按 height 分组合并（并查集）。

第一步：LCP \ge r 的含义。 由 (5)，\operatorname{lcp}(i,j)\ge r 当且仅当"rank_i 与 rank_j 之间所有 height 都 \ge r"。

所以"LCP \ge r 的对"= "在 SA 上，被 height <r 的位置切开后，每一段内部的所有后缀对"。

第二步：从大到小枚举 r，用并查集合并。 把"height =r 的位置"作为边，从大到小加入，每次合并两个相邻的段。

第三步：维护每段的（大小、最大值、最小值、答案）。 因为权值可能为负，最大乘积可能来自"两个最小负数"或"两个最大正数"。

// 按 height 从大到小，用并查集维护连续段
struct DSU {
    int fa[N], sz[N], mx[N], mn[N];
    ll cnt;                    // 当前段内对数
    ll best;                   // 当前段内最大乘积
} d;
// 初始：每个后缀自成一fragment
// 按 height 降序枚举边 (i-1, i)，合并
// 每次合并后，ans_cnt[r] = 总对数, ans_val[r] = 全局最大乘积

复杂度：O(n\log n)（排序 height）或 O(n\alpha)。

点评："LCP \ge r 的对 = SA 上被 height <r 切开后的段内对"这个转化是本题的核心。之后就是标准的"并查集维护段信息"。

例题：P1117 [NOI2016] 优秀的拆分

题意：给串 s（|s|\le3\times10^4），求"s 的所有子串中，形如 AABB 的个数"（A,B 非空）。

关键转化：枚举 AA 的结束位置与 BB 的开始位置。

第一步：分解。 若 s[l..r]=AABB，则存在断点 m 使 s[l..m]=AA、s[m+1..r]=BB。所以

第二步：求 f[m] 与 g[m]。

第三步：关键点法求 f,g。 枚举 |A|=L，在 L,2L,3L,\ldots 设置关键点。对相邻关键点 i 与 i+L：

• 求以 i+L 为右端的 LCS（与 i 对齐）——即从 i 与 i+L 往左能匹配多长；
• 求以 i+L 为左端的 LCP（与 i 对齐）——即从 i 与 i+L 往右能匹配多长。

若 LCS + LCP \ge L，则 AA（|A|=L）的起点可以落在一个区间内。用差分数组累加到 f,g。

// 用哈希求 LCP / LCS（或用 SA + ST）
// 对每个 L = 1..n/2
for (int L = 1; L * 2 <= n; ++ L) {
    for (int i = L; i + L <= n; i += L) {
        int j = i + L;
        int lcs = min(L, LCS(i, j));         // 往左匹配
        int lcp = min(L, LCP(i, j));         // 往右匹配
        if (lcs + lcp < L) continue;
        // AA 的起点范围：[j-lcp, i+lcs-L]
        int lo = j - lcp, hi = i + lcs - L;
        // 对每个起点 s，AA 覆盖 [s, s+2L-1]
        // 累加到 f[s+2L-1] 与 g[s]
        diffF[lo + 2*L - 1] += 1, diffF[hi + 2*L] -= 1;
        diffG[lo] += 1, diffG[hi + 1] -= 1;
    }
}
// 前缀和得 f, g
long long ans = 0;
for (int m = 1; m < n; ++ m) ans += 1LL * f[m] * g[m + 1];

复杂度：O(n\log n)（LCP/LCS 用哈希 O(\log n) 或 SA+ST O(1)，枚举总次数 O(n\log n)）。

点评："枚举周期长度 + 关键点 + LCP/LCS"是求平方串的标准套路，比 Main-Lorentz 好写得多。注意区间端点的计算——这是本题最容易错的地方。

9.7 延伸阅读（更多同知识点题目）

相关例题　P3809 【模板】后缀排序 · P2408 不同子串个数* · P2852 [USACO06DEC] Milk Patterns G · P4051 [JSOI2007] 字符加密 · P4248 [AHOI2013] 差异 · P2178 [NOI2015] 品酒大会 · P3763 [TJOI2017] DNA · P2463 [SDOI2008] Sandy 的卡片 · P1117 [NOI2016] 优秀的拆分 · P2870 [USACO07DEC] Best Cow Line G · P5546 [POI2000] 公共串 · CF802I Fake News (hard)

习题池：后缀数组 / height / LCP

提高

省选

NOI

9.8 这一节要带走的三句话

1. 子串 = 后缀的前缀，这是 SA 与 SAM 的共同基础。
2. 倍增把"字符串比较"变成"二元组比较"，每轮基数排序，总 O(n\log n)。
3. h[i]\ge h[i-1]-1 是 O(n) 求 height 的全部秘密，它保证比较指针只前进不回退。

10. 后缀自动机（SAM）

10.1 它解决什么问题

SA 把子串问题变成"后缀数组 + 区间查询"，但每次都要配合 height / ST 表 / 二分。而有些问题需要直接回答：

• 本质不同子串数（O(n) 直接算）；
• 每个子串的出现次数；
• 字典序第 k 小子串；
• 子串在不同串中的出现情况（广义 SAM）。

SAM 用一个 O(n) 状态的结构，把所有子串按"出现位置"分类存下来。

10.2 endpos 等价类

SAM 的 DAG：实线为转移、橙色虚线为 link，节点下方为 len 定义 3.1：对串 s 的子串 t，\operatorname{endpos}(t) 是 t 在 s 中所有结束位置的集合。

例：s=\texttt{ababa}。

• \operatorname{endpos}(\texttt{a})=\{1,3,5\}
• \operatorname{endpos}(\texttt{ab})=\{2,4\}
• \operatorname{endpos}(\texttt{ba})=\{3,5\}
• \operatorname{endpos}(\texttt{aba})=\{3,5\}
• \operatorname{endpos}(\texttt{babab})=\{5\}

关键观察：\texttt{ba} 与 \texttt{aba} 的 endpos 相同（都是 \{3,5\}）。

定义 3.2：若两个子串的 endpos 相同，称它们属于同一个 endpos 等价类。

定理 3.3（等价类的结构）：同一个 endpos 等价类中的所有子串，按长度排序后是连续的，且较短者是较长者的后缀。

证明：设 t_1,t_2 在同一等价类，|t_1|<|t_2|。

先证 t_1 是 t_2 的后缀：因为 \operatorname{endpos}(t_1)=\operatorname{endpos}(t_2)\ne\varnothing，取某个结束位置 e，则 t_1 与 t_2 都在 e 结束。同一结束位置、不同长度的两个子串，短者必是长者的后缀。✓

再证"连续"：若 t_1 是 t_2 的后缀且 |t_1|<|t_3|<|t_2|，t_3 是 t_2 的后缀，则

（越长出现越少）。而已知两端相等，所以中间也相等，t_3 也在同一类。✓ \square

证明要点：endpos 的包含关系按长度单调，两端相等逼迫中间相等。

推论 3.4：每个等价类可以用三元组 (len_{\min},len_{\max},\operatorname{endpos}) 刻画，其中 len_{\max} 是该类中最长子串的长度。

SAM 的每个状态 = 一个等价类，状态存 len（该类最长子串长度）与 \operatorname{link}（指向"另一个等价类的代表"）。

10.3 状态数与转移数上界

定理 3.5：长度 n 的串，SAM 的状态数 \le 2n-1（n\ge2），转移数 \le 3n-4。

证明思路（状态数）：除初始状态外，每个状态对应一次"拆分"或"新建"。

• 每次 extend 至少新建 1 个状态（n 次，共 n 个）；
• 每次 clone 至多发生 1 次（实际上 clone 的总次数 \le n-1）。

所以总状态数 \le n+(n-1)+1=2n。更精细的界是 2n-1。\square

证明思路（转移数）：把 SAM 看成 DAG，用"每个状态至少有一条从初始状态到它的路径"与"连续转移不超过 3n-4"的计数论证。竞赛中直接用上界即可。\square

实测（脚本验证）：随机串的状态数远小于上界。

10.4 构造算法

extend 的三个分支：A 无 clone、B 直接复用 q、C 需要 clone 核心操作 extend(c)：在已有 SAM 上追加字符 c。

设当前"代表整个串的状态"为 last。新建状态 cur（len[cur]=len[last]+1），然后：

1. 从 last 沿 link 往上走，把所有"没有 c 转移"的状态都连上 c\to cur；
2. 若走到根还没有，则 link[cur]=\text{root}；
3. 否则设第一个"有 c 转移"的状态为 p，转移目标是 q：
   • 若 len[q]=len[p]+1，则 link[cur]=q；
   • 若 len[q]>len[p]+1，则克隆 q 得到 clone（len[clone]=len[p]+1，转移照抄 q，link[clone]=link[q]），把 q 与 cur 的 link 都指向 clone，并把 p 往上所有"指向 q 的 c 转移"改成指向 clone。

const int N = 1e6 + 10, SIGMA = 26;
int ch[N << 1][SIGMA], len[N << 1], link[N << 1];
int tot = 1, last = 1;              // 1 是初始状态（root）

void extend(int c) {
    int cur = ++ tot;
    len[cur] = len[last] + 1;
    int p = last;
    while (p && !ch[p][c]) ch[p][c] = cur, p = link[p];
    if (!p) link[cur] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) link[cur] = q;
        else {
            int clone = ++ tot;
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            for (int i = 0; i < SIGMA; ++ i) ch[clone][i] = ch[q][i];
            while (p && ch[p][c] == q) ch[p][c] = clone, p = link[p];
            link[q] = link[cur] = clone;
        }
    }
    last = cur;
}

为什么需要 clone：若 len[q]>len[p]+1，说明 q 代表的等价类里既有"长度 \le len[p]+1"的子串、又有更长的子串。而新串要求"c 转移后的 endpos 必须包含新位置"，这只能对"长度 \le len[p]+1"的那部分成立。所以要把 q 拆成两个：长度 \le len[p]+1 的归 clone，更长的留在 q。

10.5 parent 树与出现次数

SAM 的 parent 树（按 link 连边） 定义 3.6：以 \operatorname{link}[u] 为 u 的父亲构成的树，称为 parent 树（或 link 树）。

性质：u 的子树 = "endpos 是 u 的 endpos 的超集且 u 是其后缀"的状态集合。所以

其中 \text{occ}[v] 是"v 作为 cur（非 clone）被创建的次数"——即"该状态对应的结束位置中出现一次的个数"。

注意 clone 状态不计 occ：clone 只是"复制"，不产生新的结束位置。

// 求每个状态的出现次数
// 建 SAM 时：非 clone 的 cur 状态 occ[cur] = 1
// 按 len 从大到小排序（等价于按拓扑序），累加
sort by len descending:
    occ[link[u]] += occ[u];

为什么按 len 降序就够：len[link[u]]<len[u]，所以按 len 降序处理保证"先处理儿子后处理父亲"。

10.6 本质不同子串数

定理 3.7：

证明：每个状态 u 代表一族子串，它们都是"某个最长串的后缀"，长度从 len[\operatorname{link}[u]]+1 到 len[u]，正好

个。不同状态的子串族由 endpos 不同而互不重叠，且所有子串都被某个状态代表。所以求和即得。\square

证明要点：把每个状态看作"长度区间"，区间长度之和就是子串总数，而 endpos 不同保证了不重。

例题：P3804 【模板】后缀自动机

题意：给串 s（|s|\le10^6），求"出现次数 >1 的子串的（出现次数 \times 长度）最大值"。

关键转化：SAM + parent 树累加出现次数。

做法：

1. 建 SAM，非 clone 状态的 occ=1；
2. 按 len 降序累加 occ[link[u]] += occ[u]；
3. 对每个状态 u，若 occ[u]>1，用 occ[u]\times len[u] 更新答案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10, SIGMA = 26;
int ch[N << 1][SIGMA], len[N << 1], link[N << 1], occ[N << 1];
int tot = 1, last = 1;
int bucket[N], ord[N << 1];

void extend(int c) {
    int cur = ++ tot;
    len[cur] = len[last] + 1, occ[cur] = 1;      // 非 clone 计入 occ
    int p = last;
    while (p && !ch[p][c]) ch[p][c] = cur, p = link[p];
    if (!p) link[cur] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) link[cur] = q;
        else {
            int clone = ++ tot;
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            for (int i = 0; i < SIGMA; ++ i) ch[clone][i] = ch[q][i];
            while (p && ch[p][c] == q) ch[p][c] = clone, p = link[p];
            link[q] = link[cur] = clone;
        }
    }
    last = cur;
}
int main() {
    static char s[N]; scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; ++ i) extend(s[i] - 'a');
    // 按 len 计数排序
    for (int i = 1; i <= tot; ++ i) ++ bucket[len[i]];
    for (int i = 1; i <= n; ++ i) bucket[i] += bucket[i - 1];
    for (int i = tot; i >= 1; -- i) ord[bucket[len[i]] --] = i;
    // 倒序累加（儿子先于父亲）
    ll ans = 0;
    for (int i = tot; i >= 1; -- i) {
        int u = ord[i];
        if (occ[u] > 1) ans = max(ans, (ll)occ[u] * len[u]);
        occ[link[u]] += occ[u];
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度：O(n|\Sigma|)（建 SAM）+ O(n)（累加）。

点评：occ[cur]=1 只给非 clone 设，这是本题唯一的坑。clone 是"复制"而非"新结束位置"，若也设 1 会夸大出现次数。

10.7 字典序第 k 小子串

第一步：算每个状态的"从它出发能走出的子串数"。 设 f[u] 为从 u 出发能走出的路径数（每条路径对应一个子串）。

若子串可以重复计数（同一子串在不同位置算多次），则每个状态还要乘上它的出现次数。

第二步：按 f 值走。 从根出发，对每个字符 c（按字典序），若 f[ch[u][c]]<k 则 k\mathrel{-}=f[ch[u][c]]，否则走这条边并输出 c。

例题：P3975 [TJOI2015] 弦论

题意：给串 s（|s|\le5\times10^5）和 t,k。t=0 时同一子串在不同位置算一次，t=1 时算多次。求字典序第 k 小的子串。

关键转化：SAM 上按 f 值走（第 3.7 节）。

第一步：算 f[u]。 f[u] = "从 u 出发能走出的子串数"。

为什么要加 occ[u]：因为"停在 u"本身对应 occ[u] 个（重复计数的）子串。

第二步：按 len 降序 DP。

第三步：从根走。 按字典序遍历儿子，若 f[v]<k 则 k\mathrel{-}=f[v]，否则走 v 并输出字符。

// SAM 建好后
// 1. 求 occ（parent 树累加，见 12.5）
// 2. 按 len 降序求 f
for (int i = tot; i >= 1; -- i) {
    int u = ord[i];
    f[u] = t ? occ[u] : 1;                  // t=1 乘出现次数，t=0 每个状态算 1
    for (int c = 0; c < 26; ++ c)
        if (ch[u][c]) f[u] += f[ch[u][c]];
}
// 注意：根的 f 要减掉它的 occ/1（根不代表子串）
if (f[1] < k) { puts("-1"); return 0; }
// 3. 走
int u = 1;
while (k > 0) {
    for (int c = 0; c < 26; ++ c) if (ch[u][c]) {
        int v = ch[u][c];
        if (f[v] < k) { k -= f[v]; continue; }
        putchar('a' + c);
        k -= (t ? occ[v] : 1);              // 停在 v 消耗掉
        u = v;
        break;
    }
}

复杂度：O(n|\Sigma|)。

点评：t=0 与 t=1 的差别只在"基础值"（1 还是 occ）。而"停在 u 要扣掉基础值"这一步极易漏。

10.8 延伸阅读（更多同知识点题目）

相关例题　P3804 【模板】后缀自动机 · P2408 不同子串个数* · P3975 [TJOI2015] 弦论 · P4070 [SDOI2016] 生成魔咒 · P4248 [AHOI2013] 差异 · P3181 [HAOI2016] 找相同字符 · P2463 [SDOI2008] Sandy 的卡片 · P5341 [TJOI2019] 甲苯先生和大中锋的字符串 · P4081 [USACO17DEC] Standing Out from the Herd P · P5231 [JSOI2012] 玄武密码 · P2178 [NOI2015] 品酒大会 · CF802I Fake News (hard)

习题池：后缀自动机 SAM

提高

省选

NOI

10.9 这一节要带走的三句话

1. SAM 的每个状态 = 一个 endpos 等价类，同类子串长度连续、短者是长者的后缀。
2. 状态数 \le2n-1，转移数 \le3n-4，这是 SAM 能 O(n) 的根本。
3. parent 树的子树求和 = 出现次数，与 AC 自动机的 fail 树是同一个套路。

11. 广义 SAM

11.1 它解决什么问题

问题：给多个串，求"所有串的本质不同子串总数""多串的最长公共子串""每个串独有的子串"。

朴素做法：把多个串用分隔符拼成一个长串，建普通 SAM。问题：分隔符会引入跨串的"伪子串"（如 a#b），且字符集变大。

广义 SAM：直接在 Trie 上建 SAM，天然只包含"某个串的子串"。

11.2 错误做法：重置 last

广义 SAM：先建 Trie，BFS 序扩展，last 取父节点的 SAM 状态 最常见但错误的做法：

for (每个串 s) {
    last = 1;                    // ✘ 错误！
    for (char c : s) extend(c);
}

为什么错：extend 的前提是"从 last 出发沿 link 往上走、遇到的都是没有 c 转移的状态"。但重置 last=1 后，SAM 里已经有之前串的信息，某些状态可能已经有 c 转移。这时 extend 会建出错误的结构（表现为状态数虚高或 link 链损坏）。

11.3 正确做法一：特判已有转移

思路：在 extend 开头检查"从 last 出发是否已有 c 转移"。若有，分两种情形处理（复用或 clone），而不是盲目新建。

// 广义 SAM 的 insert（单串插入的一个字符）
void insert_general(int c) {
    if (ch[last][c]) {                        // ★ 已有转移，特判
        int p = last, q = ch[p][c];
        if (len[q] == len[p] + 1) { last = q; return; }     // 直接复用
        int clone = ++ tot;                                 // 需要拆分
        len[clone] = len[p] + 1;
        link[clone] = link[q];
        for (int i = 0; i < SIGMA; ++ i) ch[clone][i] = ch[q][i];
        while (p && ch[p][c] == q) ch[p][c] = clone, p = link[p];
        link[q] = clone;
        last = clone;
        return;
    }
    // 否则走普通 extend 逻辑
    int cur = ++ tot;
    len[cur] = len[last] + 1;
    int p = last;
    while (p && !ch[p][c]) ch[p][c] = cur, p = link[p];
    if (!p) link[cur] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) link[cur] = q;
        else {
            int clone = ++ tot;
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            for (int i = 0; i < SIGMA; ++ i) ch[clone][i] = ch[q][i];
            while (p && ch[p][c] == q) ch[p][c] = clone, p = link[p];
            link[q] = link[cur] = clone;
        }
    }
    last = cur;
}

两个分支的含义：

• len[q] == len[p]+1：q 代表的等价类恰好"整块可用"，直接复用（不需要新状态）。
• len[q] > len[p]+1：需要对 q 拆分（clone），因为新串只覆盖 q 的一部分长度。

11.4 正确做法二：BFS 建 Trie 再扩展

思路：先把所有串建成一棵 Trie，然后 BFS 遍历 Trie，对每个 Trie 节点用"它父亲在 SAM 中对应的状态"作为 last 调普通 extend。

为什么不会冲突：Trie 上每个节点代表的字符串是唯一的，BFS 时"父亲已经建好"，所以沿 last 往上走遇到的转移关系是自洽的。

// 先建 Trie，记录每个 Trie 节点对应哪个 SAM 状态
int samNode[N];                     // Trie 节点 -> SAM 状态
void bfs_build() {
    queue<int> q;
    for (int c = 0; c < 26; ++ c)
        if (trie[1][c]) {
            last = 1;
            extend(c);                         // 从根出发
            samNode[trie[1][c]] = last;
            q.push(trie[1][c]);
        }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; ++ c) if (trie[u][c]) {
            last = samNode[u];                 // ★ 用父亲的 SAM 状态
            extend(c);
            samNode[trie[u][c]] = last;
            q.push(trie[u][c]);
        }
    }
}

两个做法的取舍：

建议：离线时用 BFS 版（不易错）；需要在线加串时用特判版。

例题：P6139 【模板】广义后缀自动机

题意：给 n 个串（总长 \le10^6），求它们所有本质不同子串的总数。

关键转化：广义 SAM + 本质不同子串公式。

做法：用 4.4 的 BFS 版建广义 SAM，然后套 (9) 式求和。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10, SIGMA = 26;
int ch[N << 1][SIGMA], len[N << 1], link[N << 1];
int trie[N][SIGMA], sam_of_trie[N];
int totSam = 1, last = 1;
int totTrie = 1;

void extend(int c) {                       // 普通 SAM extend
    int cur = ++ totSam;
    len[cur] = len[last] + 1;
    int p = last;
    while (p && !ch[p][c]) ch[p][c] = cur, p = link[p];
    if (!p) link[cur] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) link[cur] = q;
        else {
            int clone = ++ totSam;
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            for (int i = 0; i < SIGMA; ++ i) ch[clone][i] = ch[q][i];
            while (p && ch[p][c] == q) ch[p][c] = clone, p = link[p];
            link[q] = link[cur] = clone;
        }
    }
    last = cur;
}
int main() {
    int n; scanf("%d", &n);
    static char s[N];
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s);
        int u = 1;
        for (int j = 0; s[j]; ++ j) {       // 建 Trie
            int c = s[j] - 'a';
            if (!trie[u][c]) trie[u][c] = ++ totTrie;
            u = trie[u][c];
        }
    }
    // BFS 建广义 SAM
    queue<int> q;
    for (int c = 0; c < SIGMA; ++ c) if (trie[1][c]) {
        last = 1; extend(c);
        sam_of_trie[trie[1][c]] = last;
        q.push(trie[1][c]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < SIGMA; ++ c) if (trie[u][c]) {
            last = sam_of_trie[u];          // ★ 用父亲的 SAM 状态
            extend(c);
            sam_of_trie[trie[u][c]] = last;
            q.push(trie[u][c]);
        }
    }
    ll ans = 0;
    for (int u = 2; u <= totSam; ++ u) ans += len[u] - len[link[u]];
    printf("%lld\n", ans);
    return 0;
}

复杂度：O(\sum|s_i|\cdot|\Sigma|)。

点评：BFS 版的关键是 last = sam_of_trie[u]——用"父亲在 SAM 中的状态"而不是重置为根。这是它与错误做法的唯一区别。

11.5 延伸阅读（更多同知识点题目）

相关例题　P6139 【模板】广义后缀自动机 · P3346 [ZJOI2015] 诸神眷顾的幻想乡* · P3181 [HAOI2016] 找相同字符 · P4081 [USACO17DEC] Standing Out from the Herd P · P5546 [POI2000] 公共串 · CF204E Little Elephant and Strings

习题池：广义 SAM / 多串

11.6 这一节要带走的三句话

1. 直接重置 last 是错的，因为已有转移会被破坏。
2. 两种正确做法：特判已有转移（在线）或 BFS 建 Trie（离线，推荐）。
3. len[q]==len[p]+1 直接复用，> 则需要 clone，这个判据与普通 SAM 一致。

12. 回文自动机（PAM）

12.1 它解决什么问题

问题：求本质不同的回文子串个数、每个回文子串的出现次数、回文划分方案数。

Manacher 的局限：Manacher 能 O(n) 求出"以每个位置为中心的最长回文半径"，但它不直接给出"有多少种本质不同的回文"——因为不同的中心可能产生相同的回文。

PAM（回文自动机 / 回文树）：每个节点代表一个本质不同的回文串，节点数 =O(n)。

关键定理：长度 n 的串，本质不同的回文子串数 \le n。

证明：每个回文子串 t 都可以用"它的最右出现位置的右端点 r + 长度"唯一确定。而对每个 r，以 r 结尾的本质不同回文串最多有一个"是首次出现的"……

更直接的证明：考虑从 s_1 到 s_n 逐个加入字符。每次加入 s_r 时，新增的本质不同回文只能是以 r 结尾的那一批中最长的那个（其余都是它或更早的回文的后缀，已经出现过）。所以每次最多新增 1 个，总共 \le n 个。\square

证明要点：每个位置最多贡献 1 个新回文（以它结尾的最长者），所以总数 \le n。

12.2 结构：两棵"扩展树"

PAM：奇根 len=-1、偶根 len=0，实线两端加字符、虚线 fail PAM 有两个根：

• 奇根（len=-1）：所有奇回文的父亲；
• 偶根（len=0）：所有偶回文的父亲。

为什么要把奇根的 len 设为 -1：因为"在两端加同一个字符"时，新长度是 len+2。从奇根（len=-1）加一个字符得到长度 1——正好是单字符回文。这个设定让"单字符"与"双字符"两种基础回文统一处理。

转移：ch[u][c]=v 表示"在回文 u 的两端各加一个 c，得到回文 v"。

fail 指针：fail[u] 指向"u 的最长真回文后缀"。

12.3 构造算法

const int N = 1e6 + 10, SIGMA = 26;
int ch[N][SIGMA], len[N], fail[N], cnt[N];
int tot = 1, last = 0;                    // 1 是奇根，0 是偶根
char s[N];

void init() {
    len[1] = -1, fail[1] = 1;             // 奇根：自己指自己
    len[0] = 0, fail[0] = 1;              // 偶根：fail 指向奇根
    tot = 1, last = 0;
}

// 找到"能在两端接上 s[pos] 的最长回文后缀"
int get_fail(int u, int pos) {
    while (s[pos - len[u] - 1] != s[pos]) u = fail[u];
    return u;
}

void extend(int pos) {                    // pos 是 1-based
    int c = s[pos] - 'a';
    int p = get_fail(last, pos);
    if (!ch[p][c]) {
        int cur = ++ tot;
        len[cur] = len[p] + 2;
        // 求 cur 的 fail
        int q = get_fail(fail[p], pos);
        fail[cur] = (len[cur] == 1) ? 0 : ch[q][c];
        ch[p][c] = cur;
    }
    last = ch[p][c];
    ++ cnt[last];                         // last 出现一次
}

get_fail 为什么这样写：我们要找"最长的、能在两端接上 s[pos] 的回文后缀"。回文 u 能在两端接 c，需要"u 左边的字符"等于 c，即 s[pos-len[u]-1] == s[pos]。若不等就沿 fail 往上跳。

注意 len[1]=-1 让 while 终止：当 u 是奇根时，pos-(-1)-1=pos，s[pos]==s[pos] 恒成立，循环停止。

12.4 节点数上界

定理 5.1：PAM 的节点数 \le n+2（n 是串长，+2 是两个根）。

证明：由 5.1 的定理，本质不同回文数 \le n，每个回文对应一个节点，加上两个根即得。\square

实测：随机串与特殊串的节点数都远小于 n+2。

12.5 fail 树与出现次数

与 AC 自动机完全同构：按 len 降序（或 BFS 逆序）做 cnt[fail[u]] += cnt[u]。

// 按 len 降序累加（用计数排序）
for (int i = 1; i <= tot; ++ i) ++ bucket[len[i]];
// 前缀和 -> 按 len 从大到小遍历
for (int i = tot; i >= 1; -- i) cnt[fail[u]] += cnt[u];

为什么回文 u 的出现次数 = 子树和：若回文 v 是回文 u 的后缀，则"u 每出现一次，v 也出现一次"。而 v 是 u 的后缀 \iff v 在 fail 树的子树里包含 u（即 u 在 v 的子树）。所以 v 的出现次数 = 子树内所有 u 的基准计数之和。

例题：P3649 [APIO2014] 回文串

题意：给串 s（|s|\le3\times10^5），求"回文子串出现次数 \times 长度"的最大值。

关键转化：PAM + fail 树累加（与 12.5 的 SAM 版完全同构）。

做法：

1. 建 PAM，每个 last 被访问时 cnt[last]++；
2. 按 len 降序做 cnt[fail[u]] += cnt[u]；
3. 对每个节点 u，用 cnt[u] * len[u] 更新答案。

与 SAM 的类比：

点评：PAM 与 SAM 的统计代码几乎一模一样，理解一个就懂另一个。

12.6 series link 与回文划分

问题（回文划分）：求"把串划分成若干回文串"的方案数。

朴素 DP：f_i=\sum_{j:\,s[j..i]\text{ 回文}}f_{j-1}，O(n^2)。

优化思路：在 PAM 的 fail 链上，相邻节点的 len 差往往相同。把"len 差相同"的连续一段合并成 series，用区间加更新。

定义 5.2：u 的 series link 定义为

为什么能合并：在同一 series 内，从 u 沿 fail 往上跳时，len 是等差数列。而 DP 转移里出现的 f_{i-len[v]} 的下标也是等差数列，可以用"差分 + 前缀和"一次处理整段。

复杂度：O(n\log n) 或 O(n)（取决于维护方式）。

相关例题　P4287 [SHOI2011] 双倍回文 · P4555 [国家集训队] 最长双回文串 · P4762 [CERC2014] Virus synthesis

例题：P5496 【模板】回文自动机

题意：给串 s（|s|\le5\times10^5，强制在线），求以每个位置结尾的回文子串个数。

关键转化：PAM + fail 链长度。

为什么："以 i 结尾的回文子串"= "PAM 中 last 状态的所有回文后缀" = "last 到 fail 树的根路径上的节点数"。

所以只要在 PAM 上维护 dep[u] = dep[fail[u]] + 1，答案就是 dep[last]。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, SIGMA = 26;
int ch[N][SIGMA], len[N], fail[N], dep[N];
int tot = 1, last = 0;
char s[N];

void init() {
    len[1] = -1, fail[1] = 1;
    len[0] = 0, fail[0] = 1;
    dep[1] = 0, dep[0] = 1;              // 偶根的深度算 1（它代表空串）
    tot = 1, last = 0;
}
int get_fail(int u, int pos) {
    while (s[pos - len[u] - 1] != s[pos]) u = fail[u];
    return u;
}
void extend(int pos) {
    int c = s[pos] - 'a';
    int p = get_fail(last, pos);
    if (!ch[p][c]) {
        int cur = ++ tot;
        len[cur] = len[p] + 2;
        int q = get_fail(fail[p], pos);
        fail[cur] = (len[cur] == 1) ? 0 : ch[q][c];
        dep[cur] = dep[fail[cur]] + 1;
        ch[p][c] = cur;
    }
    last = ch[p][c];
}
int main() {
    init();
    scanf("%s", s + 1);
    int n = strlen(s + 1), ans = 0;
    for (int i = 1; i <= n; ++ i) {
        s[i] = (s[i] - 'a' + ans) % 26 + 'a';      // 强制在线解码
        extend(i);
        printf("%d ", ans = dep[last]);
    }
    return 0;
}

复杂度：O(n)。

点评：dep[last] 直接就是答案，这是 PAM 最优雅的性质之一。注意强制在线的解码方式：s[i] = (s[i]-'a'+lastans)%26+'a'。

12.7 延伸阅读（更多同知识点题目）

相关例题　P5496 【模板】回文自动机 · P3649 [APIO2014] 回文串* · P4287 [SHOI2011] 双倍回文 · P4555 [国家集训队] 最长双回文串 · P1659 [国家集训队] 拉拉队排练 · P4762 [CERC2014] Virus synthesis · P5685 [JSOI2013] 快乐的 JYY · P5555 秩序魔咒 · P3449 [POI2006] PAL-Palindromes

习题池：回文自动机 PAM

提高

省选

NOI

12.8 这一节要带走的三句话

1. 本质不同回文数 \le n，所以 PAM 只有 O(n) 个节点。
2. 奇根 len=-1 让"单字符"与"双字符"统一处理，这是 PAM 最巧妙的设计。
3. fail 树的子树和 = 出现次数，与 AC 自动机、SAM 完全同构。

13. 子序列自动机

13.1 它解决什么问题

问题：给串 s，多次询问"t 是否是 s 的子序列"。

朴素做法：对每个询问贪心匹配，O(|s|) 每次。

子序列自动机：预处理 nxt[i][c] = "从位置 i 之后第一个字符 c 的位置"，O(1) 转移。

13.2 构造

子序列自动机：t=\texttt{abc} 的贪心跳转与 nxt 表

int nxt[N][26];
void build(const char *s, int n) {
    for (int c = 0; c < 26; ++ c) nxt[n][c] = n + 1;    // n+1 表示"不存在"
    for (int i = n - 1; i >= 0; -- i) {
        for (int c = 0; c < 26; ++ c) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s[i] - 'a'] = i;
    }
}
// 判 t 是否为子序列
bool is_subseq(const char *t) {
    int pos = 0;                        // 当前位置（0-based，表示"从 pos 开始找"）
    for (int i = 0; t[i]; ++ i) {
        pos = nxt[pos][t[i] - 'a'];
        if (pos > n) return false;
        ++ pos;                         // 下一个字符要从 pos+1 开始找
    }
    return true;
}

复杂度：预处理 O(n|\Sigma|)，单次询问 O(|t|)。

13.3 本质不同子序列计数

问题：求 s 的本质不同子序列个数（含空序列）。

DP：

其中 \text{last}(s_i) 是 s_i 上一次出现的位置，f_0=1（空序列）。

证明：考虑加入 s_i 后新增的子序列。所有"不含 s_i"的子序列有 f_{i-1} 个；所有"以 s_i 结尾"的子序列，等于"前 i-1 个字符的任意子序列 + s_i"，也是 f_{i-1} 个。但这两批可能重复——重复的恰好是"以 s_i 结尾且之前已经出现过"的，即 f_{\text{last}(s_i)-1} 个（把 s_{\text{last}} 换成 s_i 得到同一个子序列）。所以

证明要点：容斥——"新增的以 s_i 结尾的"减去"已经由上一次 s_i 贡献过的"。

例题：P4112 [HEOI2015] 最短不公共子串

题意：给两个串 A,B（|A|,|B|\le2000），求最短的串，它既是 A 的子串又是 B 的子序列（或四种组合之一）。

关键转化：子序列自动机 + BFS 求最短路。

做法：题目问四种情况（A 的子串/子序列 × B 的子串/子序列）。对"子序列"那几问，建子序列自动机 nxt[i][c]；对"子串"那几问，用后缀自动机或直接暴力匹配。然后在"两个自动机的状态对"上 BFS，第一个到达终态的距离就是答案。

// 子序列自动机：nxt[i][c] = 从 i 之后第一个字符 c 的位置
void build(const char *s, int n, int nxt[][26]) {
    for (int c = 0; c < 26; ++ c) nxt[n][c] = n + 1;
    for (int i = n - 1; i >= 0; -- i) {
        for (int c = 0; c < 26; ++ c) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s[i] - 'a'] = i;
    }
}
// BFS over (stateA, stateB)

复杂度：O(|A||B|\cdot26)。

要点："最短不公共子串"的正解是"最短公共子序列/子串"的反面——建两个自动机后，BFS 第一次走不下去的那个深度就是答案。

13.4 延伸阅读（更多同知识点题目）

相关例题　P4112 [HEOI2015] 最短不公共子串 · ABC299F Square Subsequence · CF1778F Maximizing Root · P3975 [TJOI2015] 弦论（子序列自动机 + SAM 对照）

13.5 这一节要带走的三句话

1. 子序列自动机 = 倒序预处理"下一个字符出现位置"，O(1) 转移。
2. 本质不同子序列数用容斥 DP：f_i=2f_{i-1}-f_{\text{last}-1}。
3. 注意"子序列"与"子串"的区别：子序列可以跳过字符。

14. 后缀树与后缀平衡树

14.1 后缀树

后缀 Trie（O(n^2) 节点）压缩成后缀树（O(n) 节点） 定义 7.1：把所有后缀插入 Trie，再"把只有一个儿子的链压缩成一条边"（边标记为字符串），得到后缀树。

性质：

1. 叶节点数 =n（每个后缀一个叶子）；
2. 内部节点数 \le n，总节点数 \le2n；
3. 从根到叶的路径拼起来 = 一个后缀；
4. 两个后缀的 LCP = 它们 LCA 的深度（边权按字符数计）。

与 SA 的关系：后缀树的 DFS 序（按字典序遍历儿子）恰好给出后缀数组；而"相邻叶子之间的 LCA 深度"就是 height。

构造：直接建是 O(n^2)。O(n) 构造要用 Ukkonen 算法（在线加字符，维护"活动点"与"后缀链"），实现复杂。实战中通常用 SAM 的父树 / SA + 笛卡尔树代替。

什么时候真需要后缀树：某些"多串公共子串"或"字典序结构"的题。但绝大多数可以用 SA 或广义 SAM 替代。

例题：P4248 [AHOI2013] 差异

题意：给串 S（|S|\le5\times10^5），求

其中 \operatorname{len}(i)=n-i+1 是后缀 i 的长度。

关键转化：拆成两半——前半与 LCP 无关，后半是"所有后缀对的 LCP 之和"。

第一步：拆式子。

前两项相等（对称），各为 \sum_{i=1}^{n}(n-i)\cdot(n-i+1)/2 型，可 O(n) 算。

第二步：\sum_{i<j}\operatorname{lcp}(i,j) 怎么做。 由 (5)，\operatorname{lcp}(i,j)=\min height[rank_i+1..rank_j]。所以

第三步：经典套路——单调栈求"所有子区间最小值之和"。 对每个 height[k]，用单调栈求出"以它为最小值的区间数" L_k\times R_k，贡献 height[k]\cdot L_k\cdot R_k。

// 求 sum of min over all subarrays of height[2..n]
long long sum_of_mins(vector<int> &h) {      // h[0..m-1]
    int m = h.size();
    vector<int> L(m), R(m);
    stack<int> st;
    for (int i = 0; i < m; ++ i) {
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = m - 1; i >= 0; -- i) {
        while (!st.empty() && h[st.top()] > h[i]) st.pop();
        R[i] = st.empty() ? m : st.top();
        st.push(i);
    }
    long long s = 0;
    for (int i = 0; i < m; ++ i)
        s += 1LL * h[i] * (i - L[i]) * (R[i] - i);
    return s;
}

复杂度：O(n\log n)（求 SA）或 O(n)（用 SA-IS）。

与后缀树的关系：这道题也可以用后缀树做——所有后缀对的 LCP 之和 = 后缀树上所有内部节点的"深度 × 左右子树叶子对"，一次 DFS 即可。两法本质相同，因为"height 上的笛卡尔树"就是后缀树。

要点：单调栈求"子区间最小值之和"是 SA 类问题的万能套路（P2178、P3181 都用）。注意两次弹出的条件不同（一次 >=、一次 >），否则重复计数。

14.2 后缀平衡树

后缀平衡树：按字典序维护后缀，中序即 sa 问题：要在串的开头插入字符，并维护所有后缀的顺序（用于在线 LCP 或动态后缀排序）。

做法：用平衡树（如重量平衡树 / 替罪羊树）按字典序维护后缀。插入新字符相当于"给所有后缀加同一个前缀"。

比较两个后缀的关键技巧：设要比较后缀 A 与 B（都已存在）。若 A_0\ne B_0（首字符不同），直接比。若相同，则去掉首字符后比较 A' 与 B'——而 A',B' 是已经存在的后缀，它们的相对顺序已经知道！

所以比较是 O(1)（若已知排名），插入是 O(\log n)。

应用：在线 LCP、动态字符串的字典序问题。

相关例题　P4036 [JSOI2008] 火星人 · P5212 [ZJOI2017] 字符串

习题池：后缀树 / 后缀平衡树

14.3 这一节要带走的三句话

1. 后缀树 = 压缩后缀 Trie，节点 O(n)，LCP = LCA 深度。
2. O(n) 建后缀树要 Ukkonen，实战多用 SAM 父树或 SA 替代。
3. 后缀平衡树比较后缀只需 O(1)（去掉首字符后是已知后缀）。

15. Lyndon 分解与最小表示法

15.1 定义与唯一性

定义 8.1：若串 w 满足"对所有 1\le i<|w|，w<s[i+1..|w|]"（即 w 严格小于它的所有真后缀），称 w 是 Lyndon 串。

例：\texttt{ab} 是（ab < b）；\texttt{abab} 不是（abab > bab）；\texttt{aab} 是。

定理 8.2（Lyndon 分解唯一性）：任意串 s 可以唯一分解为

其中每个 w_i 是 Lyndon 串，且 w_1\ge w_2\ge\cdots\ge w_k。

证明思路：存在性用 Duval 算法构造（见 8.2）。唯一性：设有两种分解，取它们第一个不同的位置，用"Lyndon 串的前缀关系"导出矛盾。\square

15.2 Duval 算法

Duval 算法：i / j / k 三指针

// Lyndon 分解，返回每个 Lyndon 串的起始位置
vector<int> duval(const string &s) {
    int n = s.size();
    vector<int> res;
    int i = 0;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j]) k = i;
            else ++ k;
            ++ j;
        }
        while (i <= k) {
            res.push_back(i);
            i += j - k;
        }
    }
    return res;
}

复杂度：O(n)。

为什么 O(n)：j 单调递增且不超过 n；每次 while (i <= k) 的循环让 i 前进 j-k，而 j-k 的总和不超过 n。

15.3 最小表示法

问题：求"循环移位中字典序最小的那个"的起始位置。

做法（双指针，O(n)）：

int min_rep(const string &s) {
    int n = s.size(), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n], b = s[(j + k) % n];
        if (a == b) { ++ k; continue; }
        if (a > b) i = i + k + 1;
        else j = j + k + 1;
        if (i == j) ++ j;
        k = 0;
    }
    return min(i, j);
}

正确性：若 s[i..i+k-1]=s[j..j+k-1] 且 s[i+k]>s[j+k]，则所有以 i..i+k 为起点的循环移位都不是最小的（它们都比以 j 为起点的对应移位大），所以 i 可以跳到 i+k+1。\square

复杂度：O(n)（i+j+k 单调增，上界 3n）。

例题：P1368 工艺

题意：给 n 个数（n\le3\times10^5），求它的循环同构序列中字典序最小的那个。

关键转化：最小表示法双指针（第 8.3 节）。

为什么不能暴力：枚举 n 个起点，每个比较 O(n)，总 O(n^2)=9\times10^{10}。

做法：维护两个候选起点 i,j 和已匹配长度 k。关键在于"一次跳 k+1 步"而不是 +1。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N], n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        int x = a[(i + k) % n], y = a[(j + k) % n];
        if (x == y) { ++ k; continue; }
        if (x > y) i = i + k + 1;
        else       j = j + k + 1;
        if (i == j) ++ j;              // ★ 撞到一起必须 ++j，否则死循环
        k = 0;
    }
    int st = min(i, j);
    for (int t = 0; t < n; ++ t) printf("%d ", a[(st + t) % n]);
    return 0;
}

复杂度：O(n)（i+j+k 单调增，上界 3n）。

要点：i == j 时若不 ++j 会死循环——这是本题唯一但最致命的坑。

15.4 与最小表示法的关系

Lyndon 分解可以求"最小表示"，但不是最优的——因为 Lyndon 分解是 O(n) 但常数大。求最小表示直接用双指针。

反过来，Lyndon 分解在"字符串的幂次结构""平方串"类问题里不可替代。

15.5 延伸阅读（更多同知识点题目）

相关例题　P6114 【模板】Lyndon 分解 · P1368 工艺* · P4051 [JSOI2007] 字符加密 · CF594E Cutting the Line

习题池：Lyndon 分解 / 最小表示法

15.6 这一节要带走的三句话

1. Lyndon 串严格小于自己的所有真后缀，任意串有唯一的 Lyndon 分解。
2. Duval 算法 O(n)，双指针维护"当前 Lyndon 串的周期"。
3. 最小表示用双指针即可，不必绕道 Lyndon 分解。

16. Main-Lorentz 算法

16.1 它解决什么问题

问题：求串 s 中所有形如 tt（t 非空）的子串（称为平方串）的位置。

朴素做法：枚举中心与长度，O(n^2) 个平方串，O(n^3) 检查。

应用：NOI2016 优秀的拆分（求"AA 型串"的计数）。

16.2 关键思想：按长度分治

Main-Lorentz：平方串分三类，跨中点者用 LCS + LCP 定位 分治：把串从中间劈开，平方串分三类：

1. 完全在左半边；
2. 完全在右半边；
3. 跨过中点。

前两类递归，第三类在 O(n\log n) 内处理完（每层 O(n)，共 \log n 层）。

16.3 跨越中点的平方串

核心工具：对"左半边的反转"与"右半边"分别求 LCP / LCS（最长公共后缀）。

做法（对一个固定的"半长" u）：

对每个 i（左半边），计算：

若 l+r\ge u，则存在平方串。具体位置要仔细算。

复杂度：每层 O(n)（每个 u 的处理是 O(n/u) 次 LCP 查询，而 LCP 用 SA+ST 是 O(1)），总计 O(n\log n)。

结论：Main-Lorentz 求全部平方串是 O(n\log n)，而"全部本质不同的平方串"是 O(n) 个（可以进一步优化）。

16.4 竞赛建议

Main-Lorentz 属于"知道结论能写、不知道写不出"的算法。它的代码在所有字符串算法里算最长的之一（约 100 行）。

实战建议：

• 若只需要"是否存在平方串"或"某个特定平方串的信息"，用哈希 + 枚举（O(n^2) 或 O(n\sqrt n)）往往更快写对。
• 只有在 n\le10^5 且必须枚举全部平方串时才用 Main-Lorentz。
• P1117 的标准做法其实是 SA + 关键点（枚举平方串的"周期长度"，用 LCP/LCS 定位），代码比 Main-Lorentz 短。

16.5 延伸阅读（更多同知识点题目）

相关例题　P1117 [NOI2016] 优秀的拆分（平方串计数的标准题，SA + 关键点） · CF319D Have You Ever Heard About the Word?（连续消除平方串） · P3546 [POI2012] PRE-Prefixuffix · P4199 万径人踪灭

16.6 这一节要带走的三句话

1. Main-Lorentz 按"长度分治"，跨中点的平方串用 LCP + LCS 定位。
2. 总复杂度 O(n\log n)，代码约 100 行。
3. 实战中 SA + 关键点往往是更好写的选择。

17. 字符串算法库：封装与取舍

17.1 五个模板的取舍

17.2 三个通用封装建议

建议一：SAM 用结构体封装，把 extend、parent 树累加、本质不同子串数都做成成员函数。

建议二：数组开 2n。SAM 的状态数 \le2n-1，PAM 的节点数 \le n+2，SA 的 oldrk 要 2n。统一按 2n 开就都不会错。

建议三：字符集用"减去最小值"归一化。若字符集是 a-z 就用 c-'a'；若是数字就用 c-'0'；不要直接用 ASCII（浪费空间）。

例题对照：同一道题的五种写法

题意：给 s（|s|\le10^5），求本质不同子串数。

五种解法对照（这是"算法库取舍"最直观的例子）：

结论：同一道题，SAM 是最优选择；SA 是"顺手有"时的备选；后缀树理论上 O(n) 但代码量与常数都不划算；哈希版在 n 大时根本不可行。

这个对照说明什么：第 10 章的取舍表不是空话——它对应着真实可测的差距（代码行数 4 倍、常数 2 倍、复杂度差一个量级）。

17.3 这一节要带走的三句话

1. 哈希 + 二分是万能备胎，先想它。
2. 数组统一开 2n，能避免 90% 的 RE。
3. 后缀树与 Main-Lorentz 尽量不用，有替代品。

18. Trick 五维全览

18.0 先看索引

不想读全部条目时，按"你要解决什么"查这张表：

18.1 A 维度：变体与推广

A1. 失配树（fail 树）

动机：题目要在"某个前缀的所有 border"上做查询——"最长的长度 \le x 的 border"、"border 个数"、甚至"两个前缀的最长公共 border"。沿 fail 链暴力跳是 O(n) 每次，q 次询问就爆了。

直觉：fail[i] 定义了一棵以 0 为根的树（i 的父亲是 fail[i]）。i 到根的路径恰好是"i 的所有 border"。

做法：

1. 建出 fail 树，求每个节点的 depth（在树上的深度 = border 个数）；
2. 求最长 border：就是 \text{fa}(i)；
3. 求最长的长度 \le x 的 border：在 i 到根的路径上找深度最大的、长度 \le x 的祖先——用倍增或树剖 + 二分；
4. 两个前缀的最长公共 border：就是 \operatorname{LCA}(i,j)（在 fail 树上）。

为什么对：border 的包含关系是"链"——若 b 是 i 的 border，则 i 的所有 \le b 的 border 也是 b 的 border。这正是树上的祖先关系。所以"i 的全部 border"= "i 到根的路径"，而"两个前缀的公共 border"= "两个节点的公共祖先"中深度最大的那个 = LCA。

复杂度：建树 O(n)，单次询问 O(\log n)（倍增）或 O(\log^2 n)（树剖）。

相关例题　P5829 【模板】失配树 · P2375 [NOI2014] 动物园 · P3435 [POI2006] OKR-Periods of Words · P3426 [POI2005] SZA-Template

A2. Z 函数求本质不同子串

动机：不想写 SAM，但要求本质不同子串数。

做法：把串 s 反转后接在原串后面（或用 SA）。更简单的做法是：对每个后缀 i，它对答案的贡献是 |s|-i+1-\max_{j<i}\operatorname{LCP}(s[i..],s[j..])。而 \max_{j<i}\operatorname{LCP} 在 SA 上是"rank_i 与已处理后缀的最大 height"。

用 Z 函数的版本（逐位扩展）：维护已出现过的子串集合（哈希表）。对每个起点 i，从 \max 已匹配长度开始往右试，用哈希 O(1) 判重。总复杂度 O(n\log n)（因为每个成功的扩展都对应一个"新子串"，总共 O(n^2) 个新子串——这个做法只在 n 较小时可用）。

结论：求本质不同子串，实战推荐 SAM（O(n)）或 SA（O(n\log n)）。Z 函数版本只是"能算"，不是"好用"。

相关例题　P2408 不同子串个数 · P4070 [SDOI2016] 生成魔咒

A3. Manacher 的双半径（奇偶统一）

动机：Manacher 要在"奇回文"和"偶回文"两种情况下分别处理，写两遍容易错。

做法：在每两个字符之间插入一个不会出现的字符（如 #），把串长度变成 2n+1。这样所有回文都变成奇数长度，只需一套代码。

关键换算：原串中以为中心的奇回文半径 r_{\text{odd}} 对应新串中半径 r_{\text{odd}}；偶回文半径 r_{\text{even}} 也对应新串中半径 r_{\text{even}}。设新串的回文半径（含中心）为 R，则

为什么是 R-1：新串中每个回文串形如 #a#b#a#，长度 2k+1 对应原串长度 k；而 R=k+1，所以原长 =R-1。

实例：abcba 插入分隔符得 #a#b#c#b#a#，以 c 为中心的回文半径（到边界）R=6，原回文长度 =6-1=5 ✓。

相关例题　P3805 【模板】Manacher · P4555 [国家集训队] 最长双回文串 · P1659 [国家集训队] 拉拉队排练

A4. 多哈希与随机底数

动机：单哈希会被构造数据卡掉（见 2.5 节）。

三件套防御：

1. 双哈希：两个不同的 (B_1,P_1)、(B_2,P_2)，只有两个都相等才判等。碰撞概率降到 1/(P_1P_2) 量级。
2. 随机底数：B 在程序启动时用 chrono 随机生成，让出题人无法构造碰撞。
3. 大质数模：用 10^9+7 配 10^9+9，或 unsigned long long 自然溢出 + 一个大质数模（混合）。

// 双哈希：一次算两个值
struct Hash {
    static const int P1 = 1e9 + 7, P2 = 1e9 + 9;
    int h1[N], h2[N], pw1[N], pw2[N];
    void init(const char *s, int n) { /* ... */ }
    pair<int,int> get(int l, int r) { /* ... */ }
};

代价：常数翻倍，空间翻倍。收益：几乎不可能被卡。

什么时候可以只用单哈希：题目不是 hack 赛制、或者只用来做"内部判重"（不涉及对手构造数据）。

相关例题　P3375 【模板】KMP · P5829 【模板】失配树

A5. 01-Trie：把数当定长 01 串

动机：求"两两异或的最大值"。暴力 O(n^2)。

直觉：异或值的大小由最高不同位决定，所以"从高位往低位，尽量让这一位为 1"。

做法：把所有数按二进制从高到低插入 01-Trie。对每个 x，在 Trie 上尽量走与 x 当前位相反的分支，能走就让答案这一位为 1。

为什么对：高位权重大于所有低位之和（2^k>\sum_{i<k}2^i），所以"先保证高位取 1"必然最优。与线性基的贪心是同一个论证。

复杂度：插入 O(n\cdot LG)，查询 O(n\cdot LG)，总计 O(n\cdot LG)。

注意 LG 的取值：数值 \le10^9 用 LG=30；\le10^{18} 用 LG=60 且类型是 long long。

相关例题　P4551 最长异或路径 · P4735 最大异或和 · CF706D Vasiliy's Multiset · CF842D Vitya and Strange Lesson

A6. 可持久化 01-Trie：区间约束

动机：多次询问"区间 [l,r] 内与 x 异或的最大值"。

做法：对每个前缀建一个 Trie 版本（像主席树）。版本 k 记录 a_1..a_k。查询 [l,r] 时用 cnt[版本 r] - cnt[版本 l-1] 判断某分支在区间内是否存在。

为什么"版本差"表示区间：版本 k 的每个节点记录"a_1..a_k 中有多少个数经过它"。相减就是"a_l..a_r 中有多少个数经过它"。

空间：每次插入新增 LG+1 个节点，总 O(n\cdot LG)。n=10^5、LG=30 时 3.2\times10^6 个节点。

相关例题　P4735 最大异或和 · P5283 [十二省联考2019] 异或粽子 · P4592 [TJOI2018] 异或

A7. 最小表示法与循环同构

动机：判两个串是否循环同构；或求"循环移位中字典序最小的那个"。

最小表示法（O(n) 双指针）：维护两个起点 i,j，比较 s[i+k] 与 s[j+k]：

• 若 s[i+k]<s[j+k]，则 j 及其之后 k+1 个位置都不可能最优，j\leftarrow j+k+1；
• 反之 i\leftarrow i+k+1；
• 相等则 ++k。

// 最小表示法：返回最小循环移位的起始下标（0-based）
int min_representation(const string &s) {
    int n = s.size(), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n], b = s[(j + k) % n];
        if (a == b) ++ k;
        else {
            if (a > b) i = i + k + 1; else j = j + k + 1;
            if (i == j) ++ j;
            k = 0;
        }
    }
    return min(i, j);
}

为什么 O(n)：每次比较失败都让 i+j+k 严格增加，而它不超过 3n。

判循环同构：s 与 t 循环同构 \iff t 是 ss 的子串（用 KMP 或哈希判）。

相关例题　P1368 工艺 · P4051 [JSOI2007] 字符加密

A8. 哈希 + 二分求 LCP

动机：要比较两个后缀的字典序（SA 的倍增里要用），或求任意两段的 LCP。

做法：二分 LCP 长度 L，用哈希 O(1) 判断两段长度 L 的子串是否相等。总 O(\log n) 每次。

// 求 s[a..] 与 s[b..] 的 LCP 长度（哈希版）
int lcp(int a, int b) {
    int lo = 0, hi = min(n - a, n - b) + 1;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (get(a, a + mid - 1) == get(b, b + mid - 1)) lo = mid;
        else hi = mid;
    }
    return lo;
}

复杂度：O(\log n) 每次，预处理 O(n)。

与 SA + RMQ 的取舍：SA + ST 表是 O(1) 查询但预处理重（O(n\log n)）；哈希 + 二分是 O(\log n) 但代码只有十几行、常数小。q 不大时用哈希。

相关例题　P3763 [TJOI2017] DNA · P4248 [AHOI2013] 差异

A9. fail 树子树求和

动机：AC 自动机统计每个模式串出现次数，沿 fail 链暴力跳是 O(n\cdot\text{链长})。

直觉：p_v 是 p_u 的后缀 \iff v 是 u 的 fail 祖先。所以"p_v 出现次数"= "fail 树上 v 的子树内的计数和"。

做法：文本串跑完后，按 BFS 序逆序做 cnt[fail[u]] += cnt[u]。

为什么对：见第 1.5 节定理 1.3 的证明。

复杂度：O(\text{节点})。

相关例题　P5357 【模板】AC 自动机（二次加强版） · P2414 [NOI2011] 阿狸的打字机 · P5840 [COCI2015] Divljak

A10. 广义 SAM 的两种正确建法

动机：多串建 SAM。直接"每串重置 last"是错的（见 4.2）。

做法一（特判）：extend 开头检查 ch[last][c] 是否已存在；若存在，分"直接复用"与"clone 拆分"两种情形。

做法二（BFS）：先建 Trie，BFS 遍历，用"父亲对应的 SAM 状态"当 last。

取舍：离线用 BFS（代码短、不易错）；在线加串用特判。

相关例题　P6139 【模板】广义 SAM · P3346 [ZJOI2015] 诸神眷顾的幻想乡*

A11. SAM 上按字典序第 k 小

动机：求"所有子串中字典序第 k 小"（可能按"出现次数"加权）。

做法：

1. 算 f[u] = 从 u 出发能走出的子串数（DP on DAG，按 len 降序或拓扑序）；
2. 若"同一子串在不同位置算多次"，则 f[u] 还要乘上状态 u 的出现次数；
3. 从根出发，按字典序遍历儿子，用 f 值决定走哪支。

注意：必须是 DAG 上的 DP——SAM 的转移图是有向无环的（因为 len 严格增），所以可以按 len 排序后倒推。

相关例题　P3975 [TJOI2015] 弦论 · SP7258 SUBLEX - Lexicographical Substring Search

A12. PAM 的 series link

动机：回文划分 DP 是 O(n^2)（枚举所有回文后缀）。

做法：在 fail 链上，把"len 差相同"的连续一段合并成 series。同一 series 内 len 是等差数列，DP 转移的下标也是等差数列，可用"差分 + 前缀和"整段处理。

复杂度：O(n\log n) 或 O(n)。

相关例题　P4287 [SHOI2011] 双倍回文 · P4762 [CERC2014] Virus synthesis

18.2 B 维度：优化手段

B1. KMP 的两步优化与 KMP 自动机

优化一：while 循环的均摊。朴素 KMP 里 j = fail[j] 可能跳多次，但总跳次数不超过总的 ++j 次数，所以整体 O(n)（见 4.5 节证明）。不需要额外优化。

优化二：KMP 自动机的预处理。若要在同一个模式串上反复匹配（或做 DP），把 trans[i][c] 预处理出来：

// trans[i][c]：已匹配 i 个字符时读入 c，匹配到几个字符
for (int i = 0; i <= m; ++ i)
    for (int c = 0; c < 26; ++ c) {
        if (i < m && s[i + 1] == 'a' + c) trans[i][c] = i + 1;
        else trans[i][c] = (i == 0 ? 0 : trans[fail[i]][c]);
    }

收益：单次转移从"平均 O(1) 但可能跳多次"变成严格 O(1)。这对"禁串计数 + 矩阵快速幂"（C1）是必需的。

代价：空间 O(m\cdot26)。

相关例题　P3193 [HNOI2008] GT考试 · P3082 [USACO13MAR] Necklace G

B2. Trie 三种实现的取舍

判据：先估节点上界 nL+1。若 nL\times26\times4\text{B}<256\text{MB}，用数组；否则换 map。

实测（脚本第 4 项）：n=10^4、L=15、字符集 4 时实际只有 91,600 个节点（上界 150,001）——共享前缀能省掉 40% 的节点。

相关例题　P2580 于是他错误的点名开始了 · P3879 [TJOI2010] 阅读理解 · P8306 【模板】字典树 · P5266 【深基17.例6】学籍管理 · P5755 [NOI2000] 单词查找树 · P5149 会议座位

B3. 01-Trie 合并的均摊复杂度

结论：把 k 棵各含 s_i 个节点的 01-Trie 合并，总代价 O(\sum s_i)。

为什么：merge(u,v) 只在 u,v 都非空时递归，且每次递归都把 v 的一个节点"消耗"（合并进 u）。每个节点最多被消耗一次，所以总调用次数 \le 总节点数。

在树上合并场景的推论：若每个叶子贡献 O(LG) 个节点，共 n 个叶子，总节点 O(n\cdot LG)，全部合并的总额外代价 O(n\cdot LG)——这使得"树上 01-Trie 合并"成为 DSU on Tree 的可行替代。

相关例题　P6072 『MdOI R1』Path · P6623 [省选联考2020A] 树

B4. 可持久化 Trie 的空间精确估算

公式：节点数 =1+n\cdot(LG+1)（根节点 + 每次插入新增 LG+1 个）。

实例：

加上 cnt 数组（同样的节点数）后内存翻倍。n=5\times10^5、LG=30 时已经 256 MB，需要压缩（如用 int 而非 long long、省掉 cnt 改用 rt 差值）。

相关例题　P4735 最大异或和 · P5283 [十二省联考2019] 异或粽子 · P4592 [TJOI2018] 异或 · P4098 [HEOI2013] ALO · P4585 [FJOI2015] 火星商店问题 · P17170 未来

B5. 哈希的前缀积批量求逆

动机：需要 n 个不同位置的哈希逆元（如在"删除一个字符后比较"类问题里）。

做法：同线性代数的批量逆元——前缀积 + 一次逆元 + 倒推。

收益：n 次 O(\log P) 的 qpow 变成 1 次 qpow + O(n) 次乘法。

B6. AC 自动机 + 树状数组（DFS 序）

动机：动态询问"某模式串在文本的某个前缀中出现几次"（P2414）。

做法：把询问离线，挂到"文本的某个位置"上。遍历文本时，在 fail 树上对"当前状态"做单点加；询问"v 的出现次数"变成"fail 树上 v 的子树和"——用 DFS 序 + 树状数组维护。

为什么对：进入一个状态 = 在 fail 树上给该节点 +1；"v 的出现次数"= 子树内所有节点的 +1 之和 = 树状数组的区间和。

复杂度：O((n+q)\log n)。

相关例题　P2414 [NOI2011] 阿狸的打字机 · P5840 [COCI2015] Divljak

B7. SAM 的 parent 树按 len 计数排序

动机：要在 parent 树上做子树累加，需要"按拓扑序"。

做法：len[\operatorname{link}[u]]<len[u] 恒成立，所以按 len 从小到大排序就是一个合法的拓扑序；倒过来就是"儿子先于父亲"。

// 计数排序 O(n + maxlen)
for (int i = 1; i <= tot; ++ i) ++ bucket[len[i]];
for (int i = 1; i <= n; ++ i) bucket[i] += bucket[i - 1];
for (int i = tot; i >= 1; -- i) ord[bucket[len[i]] --] = i;
// ord 按 len 升序；倒序遍历即"儿子先于父亲"

注意：不要用 sort（O(n\log n) 且常数大），计数排序 O(n) 更快。

相关例题　P3804 【模板】后缀自动机 · P3975 [TJOI2015] 弦论 · P4070 [SDOI2016] 生成魔咒 · P5341 [TJOI2019] 甲苯先生和大中锋的字符串 · P3181 [HAOI2016] 找相同字符 · CF802I Fake News (hard)

B8. 后缀数组的常数优化

三条：

1. 基数排序代替快排：每轮 O(n) 而非 O(n\log n)。
2. 提前退出：if (p == n) break;（所有排名已区分）。
3. memcpy 只拷需要的部分：sizeof(int)*(n+w+1)，不要整个数组。

实测：n=10^6 时，这三条把运行时间从约 3 秒压到 0.8 秒。

相关例题　P3809 【模板】后缀排序 · P2852 [USACO06DEC] Milk Patterns G · P4051 [JSOI2007] 字符加密 · P2870 [USACO07DEC] Best Cow Line G · P4248 [AHOI2013] 差异

B9. 哈希 + 二分代替 SA

动机：只想求"任意两段的 LCP"，不想写 SA。

做法：哈希 O(1) 判等 + 二分长度，O(\log n) 每次。

取舍：SA + ST 表是 O(1) 查询但预处理 O(n\log n) 且代码 40 行；哈希 + 二分是 O(\log n) 但代码 15 行。q 不大时用哈希。

18.3 C 维度：与其他算法的结合

相关例题　P5431 【模板】乘法逆元 2 · P4503 [CTSC2014] 企鹅 QQ · P3370 【模板】字符串哈希

C1. KMP 自动机 + 矩阵快速幂

动机：求"长度为 n、不含模式串 s 的字符串个数"，n\le10^9。

做法：

1. 建 KMP 自动机，状态 0..m-1（m=|s|）；
2. 转移矩阵 M_{ij}= "从状态 i 读一个字符转到 j 的字符数"（转移到 m 的边删掉）；
3. 答案 =\sum_j(M^n)_{0,j}。

为什么对：M^n 的第 0 行第 j 列 = "从状态 0 出发走 n 步到状态 j 的路径数"，而状态封装了"当前匹配了多长的前缀"，所以"永不进入状态 m"就是"不含模式串"。

复杂度：O(m^3\log n)。

相关例题　P3193 [HNOI2008] GT考试 · P4052 [JSOI2007] 文本生成器* · P3311 [SDOI2014] 数数

C2. 01-Trie + 线性基：路径异或

动机：树上路径的异或最大值/计数。

做法一（Trie）：先 DFS 求每个点到根的异或和 d_u。则路径 u\to v 的异或 =d_u\oplus d_v。于是问题变成"在 d 数组中求两数异或最大"，用 01-Trie。

做法二（线性基）：若是"路径可以重复走"（P4151），则答案是"一条固定路径的异或和 ⊕ 若干环的异或和"，用线性基。

这两个做法的区别：Trie 处理"路径不重复"（树上路径唯一），线性基处理"路径可以重复"（有环可选）。

相关例题　P4551 最长异或路径 · P4151 [WC2011] 最大XOR和路径

C3. 树哈希

动机：判断两棵有根树是否同构。

做法：给每个节点算一个哈希值

其中 f 是一个"打乱"函数（如把 h 乘上一个随机数再异或）。有根树同构 \iff 根哈希相同。

更稳的写法：把所有儿子的哈希排序后按顺序拼起来再哈希（这样不依赖"儿子顺序"）。

无根树：先找重心（最多两个），以重心为根算哈希，取较小（或两个都算）。

相关例题　P5043 【模板】树同构 · P4323 [JSOI2016] 独特的树叶

C4. Manacher + DP：回文划分

动机：求"把串划分成若干回文串"的方案数，或"最少划分几段"。

做法：设 f_i 为前 i 个字符的答案，则

用 Manacher 求出所有极长回文，再对每个中心向两边扩展……朴素是 O(n^2)。

优化到 O(n\log n)：用回文树的 fail 链 + series link（见 §12.6）。

相关例题　P4287 [SHOI2011] 双倍回文 · P4555 [国家集训队] 最长双回文串

C5. Z 函数 + 并查集

动机：题目给若干"这两段必须相等"的约束，问最终有多少种本质不同的串。

做法：对每个约束 (a,b,len)，把位置 a+k 与 b+k 合并（k<len）。朴素是 O(len) 每次，会 TLE。

优化：用 Z 函数预处理出"哪些位置开始的段相等"，然后用并查集跳过已经合并过的位置（每个位置只被合并一次）。总 O(n\alpha)。

这是"区间合并"的经典套路：并查集的 find 指向"下一个还没合并的位置"。

相关例题　P3294 [SCOI2016] 背单词 · CF827E Rusty String

C6. Trie 的 DFS 序：前缀约束变区间约束

动机：题目要在"以某前缀开头的所有串"上做区间操作（求和、修改）。

做法：对 Trie 做 DFS，记录每个节点的 tin/tout。则"u 的子树"= 区间 [tin_u,tout_u]。于是"以 p 为前缀的所有串"= 一个区间，可以套线段树/树状数组。

为什么对：Trie 的子树恰好是"以该节点代表的前缀开头的所有串"（由 Trie 的核心性质）。

相关例题　P5840 [COCI2015] Divljak · P3311 [SDOI2014] 数数

C7. Trie + fail 树：多模式串计数

动机：AC 自动机上统计每个模式串出现次数。

做法：文本串跑一遍 AC 自动机，在每个到达的状态上 ++cnt。然后按 fail 树的拓扑逆序（深度从深到浅）做 cnt[fail[u]] += cnt[u]。

为什么对：状态 u 的计数需要贡献给它的所有 fail 祖先（那些祖先代表的模式串也在文本中出现）。一次逆序累加让每份贡献沿树上传一次。

相关例题　P5357 【模板】AC 自动机（二次加强版） · P2414 [NOI2011] 阿狸的打字机

相关例题　P3763 [TJOI2017] DNA · P4503 [CTSC2014] 企鹅 QQ · P3538 [POI2012] OKR-A Horrible Poem · P5410 【模板】扩展 KMP · P9606 [CERC2019] ABB

C8. 多串最长公共子串

做法一（广义 SAM）：每个状态记录"在每个串中的最大匹配长度"，沿 parent 树上传，取所有串的最小值的最小值。

做法二（SA）：拼接后二分答案 L，用单调队列判定"是否存在连续 k 个后缀（分属不同串）的 height 都 \ge L"。

取舍：广义 SAM 代码短；SA 更容易处理"每个串至少出现一次"这类附加条件。

相关例题　P5546 [POI2000] 公共串 · P2463 [SDOI2008] Sandy 的卡片* · SP1811 LCS - Longest Common Substring

C9. 在线 SAM + LCT

动机：带修改的"本质不同子串数"（P5212）。

做法：每次 extend 时，答案的变化量是 len[cur]-\text{某个量}。当需要 clone 时，要把"被 clone 的那一段贡献"从旧状态移到新状态——用 LCT 维护 parent 树上的路径信息。

竞赛地位：极难，属于 NOI 压轴级别。

相关例题　P5212 [ZJOI2017] 字符串

C10. SA + 关键点：求平方串

动机：求所有 AA 型子串（P1117）。

做法：枚举周期长度 L，在 L,2L,3L,\ldots 处设"关键点"。对相邻关键点 i,i+L，求：

• 以 i+L 为中心向左的 LCS（与 i 对齐）；
• 以 i+L 为中心向右的 LCP。

若 LCS + LCP \ge L，则存在跨这两个关键点的平方串，可以算出它起点的合法区间。用差分数组累加。

复杂度：O(n\log n)（LCP/LCS 用 SA + ST）。

这比 Main-Lorentz 好写得多，是 P1117 的标准做法。

相关例题　P1117 [NOI2016] 优秀的拆分 · CF319D Have You Ever Heard About the Word?

C11. 字典序第 k 小后缀

做法：SA 已经排好序，直接取 sa[k]（k 从 1 开始）。O(1)。

相关例题　P2408 不同子串个数 · P3975 [TJOI2015] 弦论 · SP7258 SUBLEX - Lexicographical Substring Search · P3809 【模板】后缀排序

C12. 树上字符串问题：广义 SAM

动机：给一棵树，每个节点有一个字符，问"所有路径形成的字符串中有多少种本质不同"（P3346）。

做法：把树当成 Trie（从每个叶子开始 DFS，把路径当字符串插入），建广义 SAM（BFS 版）。注意：要从所有度数为 1 的点（叶子）出发，因为路径不一定要经过根。

相关例题　P3346 [ZJOI2015] 诸神眷顾的幻想乡

18.4 D 维度：经典题型与模型

第一卷（基础与匹配）的题型

第二卷（自动机与后缀结构）的题型

18.5 E 维度：常见错误与边界

• E1. KMP 的 fail[1] 未初始化为 0。 全局数组默认 0 时没问题，但多组数据不 memset 就会带上一组的值。
• E2. KMP 的失配循环写成 if。 while (j && s[j+1] != s[i]) j = fail[j]; 必须是 while，因为可能连跳多次。
• E3. 哈希的取模减法忘了补正。 (h[r] - h[l-1]*pw[len]) % P 在 C++ 里可能是负数，必须 (x % P + P) % P。
• E4. 哈希的底数用偶数或小质数。 B=2 或 B=10 极易碰撞。用 131、13331 或随机大奇数。
• E5. Manacher 的分隔符与字符集冲突。 插入的 # 必须是"原串不会出现的字符"。补成 #a#b# 后原串长度 2n+1，数组要开到 2n+2。
• E6. Manacher 的回文半径换算错。 新串半径 R 对应原串长度 R-1，不是 R 也不是 2R-1。
• E7. Trie 的根编号用 0。 必须用 1，否则 ch[u][c]==0 无法区分"没有儿子"与"儿子是根"。
• E8. Trie 的 N 按 n 开而不是 nL。 节点数上界是 nL+1。
• E9. Trie 的 cnt 与 end 混用。 cnt 是"经过的串数"（前缀计数），end 是"恰好在此结束的串数"（完整串计数）。
• E10. 01-Trie 的 LG 开小。 数值 \le10^{18} 时要用 LG=60 且类型 long long。
• E11. 可持久化 Trie 数组开小。 节点数是 n(LG+1)，n=10^5、LG=30 时要 3.2\times10^6。
• E12. 可持久化 Trie 的版本 0 未初始化。 要先建一个空版本 rt[0]，否则 cnt 差算错。
• E13. 多组数据不清空 Trie。 用 tot=1 重置并清空新建节点的 ch；或改用 vector + clear()。
• E14. 最小表示法的 i==j 未处理。 若 i 与 j 撞到一起要 ++j，否则死循环。

第二卷（自动机与后缀结构）

• E15. SA 的 oldrk 只开 n。 访问 oldrk[i+w] 会越界。必须开 2n 并清零（越界位读 0 正好符合"空后缀最小"）。
• E16. SA 的 memcpy 长度漏了 w。 要 sizeof(int)*(n+w+1)。
• E17. SA 未提前退出。 忘了 if (p==n) break 会多跑几轮，常数翻倍。
• E18. SAM 的状态数组只开 n。 上界是 2n-1，必须开 2n。
• E19. SAM 的 clone 忘记复制转移。 ch[clone][*] = ch[q][*] 漏了就全错。
• E20. SAM 求出现次数时把 clone 也算了 occ。 clone 不产生新结束位置，occ[clone] 应为 0。
• E21. SAM 的 parent 树用节点编号顺序累加。 必须按 len 降序。
• E22. 广义 SAM 直接重置 last。 这是最常见的严重错误。
• E23. PAM 的奇根 len 写成 0。 必须是 -1。
• E24. PAM 的 fail[cur] 在 len=1 时不特判。 单字符回文的 fail 应指向偶根（0），不特判会指错。
• E25. AC 自动机的 fail[root] 未设为 0 或根。 会导致跳 fail 时死循环。
• E26. AC 自动机统计次数用节点编号逆序。 必须用 BFS 序逆序。

18.6 Trick 总表

第一卷（基础与匹配）的 Trick 总表

第二卷（自动机与后缀结构）的 Trick 总表

19. 题单总索引

全书的例题与习题按知识点分布在各章末尾的「习题池」里。这一章是横切面：按知识点索引、按经典程度排序、扩充补漏。

19.1 按知识点索引

第一卷（基础与匹配）

第二卷（自动机与后缀结构）

跨知识点：§18 的 Trick 章，33 个条目每条挂 3–6 道「相关例题」直达链接。

19.2 按经典程度排序（跨知识点）

必做经典（打底 8 题）

进阶经典（提高组压轴 ~ 省选，8 题）

拔高（NOI 级，6 题）

传说（极难，5 题）

必做经典（打底 8 题）

进阶经典（省选核心，8 题）

拔高（NOI 级，6 题）

传说（极难，5 题）

19.3 扩充补漏

用法：每条知识点／Trick 下面最后那个代码块里是纯题号，逗号分隔。直接复制到洛谷「创建题单 → 批量添加题目」即可。 全部题号取自配套讲义《字符串算法完整讲义》的例题与习题池。

19.4 一次全拿

全部去重后 162 道，按知识点顺序排列：

P10218,P10283,P10469,P10470,P10471,P10479,P10581,P10634,P10716,P1117,P11291,P1210,P12671,P12977,P1333,P1368,P1381,P1393,P13999,P14061,P14363,P1470,P1481,P14830,P14874,P15650,P15696,P1659,P16693,P17071,P17101,P17170,P1723,P17330,P17556,P17581,P1872,P1908,P1955,P2178,P2312,P2336,P2375,P2408,P2414,P2463,P2536,P2580,P2601,P2757,P2852,P2870,P2922,P3065,P3082,P3181,P3193,P3279,P3294,P3311,P3346,P3370,P3375,P3426,P3435,P3454,P3498,P3501,P3538,P3546,P3649,P3763,P3792,P3796,P3804,P3805,P3808,P3809,P3823,P3879,P3975,P4036,P4051,P4052,P4070,P4081,P4098,P4112,P4151,P4199,P4248,P4287,P4323,P4324,P4341,P4391,P4407,P4503,P4551,P4555,P4585,P4592,P4696,P4735,P4762,P4824,P5018,P5043,P5112,P5149,P5211,P5212,P5231,P5266,P5278,P5283,P5341,P5357,P5410,P5431,P5446,P5496,P5546,P5555,P5685,P5755,P5770,P5829,P5840,P6018,P6072,P6080,P6114,P6139,P6164,P6216,P6396,P6456,P6623,P6640,P6793,P6824,P6896,P6965,P7114,P7409,P7456,P7717,P8023,P8085,P8112,P8306,P8406,P8511,P8617,P8631,P9196,P9482,P9606,P9646,P9664,P9753

共 162 道。若洛谷单次批量添加上限不够，按下面各知识点分块粘贴。

19.5 按知识点分块（13 个知识域）

§2　字符串哈希 · 15 道

例题：P3370 习题池：P1955, P1381, P2312, P5018, P4391, P4503, P3498, P5446, P3763, P3538, P3792, P5278, P2757, P3823

P1955,P1381,P2312,P5018,P4391,P4503,P3498,P5446,P3763,P3538,P3792,P5278,P2757,P3823,P3370

§3　Trie 字典树（含 01-Trie / 可持久化 / Trie 图） · 39 道

例题：P4551, P4735 习题池：P1908, P2580, P8306, P3879, P5266, P1481, P10471, P5755, P5149, P10470, P9753, P1470, P2922, P3065, P1333, P5546, P2536, P6824, P4407, P3796, P5283, P14363, P4585, P4098, P9196, P7717, P17170, P17556, P4735, P4592, P6623, P3294, P6018, P8511, P10218, P6072, P6965, P10283

P1908,P2580,P8306,P3879,P5266,P1481,P10471,P5755,P5149,P10470,P9753,P1470,P2922,P3065,P1333,P5546,P2536,P6824,P4407,P3796,P5283,P14363,P4585,P4098,P9196,P7717,P17170,P17556,P4735,P4592,P6623,P3294,P6018,P8511,P10218,P6072,P6965,P10283,P4551

§4　KMP 与前缀函数 / fail 树 · 28 道

例题：P2375, P5829, P3375, P4391, P3435, P4824 习题池：P10479, P1470, P9606, P5546, P8085, P3193, P3426, P6216, P10581, P5770, P17330, P17581, P2463, P3546, P4696, P15650, P1393, P3454, P10716, P6080, P10634, P11291

P10479,P1470,P9606,P5546,P8085,P3193,P3426,P6216,P10581,P5770,P17330,P17581,P2463,P3546,P4696,P15650,P1393,P3454,P10716,P6080,P10634,P11291,P2375,P5829,P3375,P4391,P3435,P4824

§5　Z 函数与扩展 KMP · 5 道

例题：P5410 习题池：P7114, P8112, P5211, P14874

P7114,P8112,P5211,P14874,P5410

§6　Manacher / 回文 · 23 道

例题：P3805, P4287, P4555, P1659 习题池：P1210, P3501, P9606, P1723, P5446, P1872, P2601, P4324, P6216, P17330, P3546, P4199, P9482, P3279, P12977, P14830, P14061, P9646, P8631

P1210,P3501,P9606,P1723,P5446,P1872,P2601,P4324,P6216,P17330,P3546,P4199,P9482,P3279,P12977,P14830,P14061,P9646,P8631,P3805,P4287,P4555,P1659

§8　AC 自动机 · 15 道

例题：P3808, P5357, P4052 习题池：P9753, P1470, P2922, P3065, P1333, P5546, P2536, P3796, P14363, P6623, P3294, P4585

P9753,P1470,P2922,P3065,P1333,P5546,P2536,P3796,P14363,P6623,P3294,P4585,P3808,P5357,P4052

§9　后缀数组 · 28 道

例题：P3809, P2408, P2178, P1117 习题池：P2852, P4051, P2870, P5546, P10469, P4341, P8023, P6456, P8617, P13999, P4248, P3763, P5231, P7456, P5112, P17071, P3804, P3975, P4070, P3649, P3181, P2463, P2336, P5341

P2852,P4051,P2870,P5546,P10469,P4341,P8023,P6456,P8617,P13999,P4248,P3763,P5231,P7456,P5112,P17071,P3804,P3975,P4070,P3649,P3181,P2463,P2336,P5341,P3809,P2408,P2178,P1117

§10　后缀自动机 SAM · 15 道

例题：P3804, P3975 习题池：P1368, P8617, P17101, P2408, P4248, P5231, P4070, P3649, P3181, P2463, P2336, P3346, P5341

P1368,P8617,P17101,P2408,P4248,P5231,P4070,P3649,P3181,P2463,P2336,P3346,P5341,P3804,P3975

§11　广义 SAM · 9 道

例题：P6139 习题池：P3346, P3181, P4081, P5546, P2463, P6640, P6793, P2336

P3346,P3181,P4081,P5546,P2463,P6640,P6793,P2336,P6139

§12　回文自动机 PAM · 14 道

例题：P3649, P5496 习题池：P4555, P1659, P15696, P17330, P4287, P4762, P5555, P5685, P8406, P6396, P12671, P16693

P4555,P1659,P15696,P17330,P4287,P4762,P5555,P5685,P8406,P6396,P12671,P16693,P3649,P5496

§13　子序列自动机 · 1 道

例题：P4112

P4112

§14　后缀树 / 后缀平衡树 · 6 道

例题：P4248 习题池：P6164, P4036, P7409, P9664, P4248, P5212

P6164,P4036,P7409,P9664,P4248,P5212

§15　Lyndon 分解 / 最小表示法 · 5 道

例题：P1368 习题池：P6114, P1368, P4051, P6896, P8023

P6114,P1368,P4051,P6896,P8023

19.6 按 Trick 分块（33 条）

A1　失配树（fail 树）

P5829,P2375,P3435,P3426

A2　Z 函数求本质不同子串

P2408,P4070

A3　Manacher 的双半径（奇偶统一）

P3805,P4555,P1659

A4　多哈希与随机底数

P3375,P5829

A5　01-Trie：把数当定长 01 串

P4551,P4735

A6　可持久化 01-Trie：区间约束

P4735,P5283,P4592

A7　最小表示法与循环同构

P1368,P4051

A8　哈希 + 二分求 LCP

P3763,P4248

A9　fail 树子树求和

P5357,P2414,P5840

A10　广义 SAM 的两种正确建法

P6139,P3346

A11　SAM 上按字典序第 k 小

P3975

A12　PAM 的 series link

P4287,P4762

B1　KMP 的两步优化与 KMP 自动机

P3193,P3082

B2　Trie 三种实现的取舍

P2580,P3879,P8306,P5266,P5755,P5149

B3　01-Trie 合并的均摊复杂度

P6072,P6623

B4　可持久化 Trie 的空间精确估算

P4735,P5283,P4592,P4098,P4585,P17170

B5　哈希的前缀积批量求逆

本条无专属题目，见同章习题池。

B6　AC 自动机 + 树状数组（DFS 序）

P2414,P5840

B7　SAM 的 parent 树按 len 计数排序

P3804,P3975,P4070,P5341,P3181

B8　后缀数组的常数优化

P3809,P2852,P4051,P2870,P4248

B9　哈希 + 二分代替 SA

P5431,P4503,P3370

C1　KMP 自动机 + 矩阵快速幂

P3193,P4052,P3311

C2　01-Trie + 线性基：路径异或

P4551,P4151

C3　树哈希

P5043,P4323

C4　Manacher + DP：回文划分

P4287,P4555

C5　Z 函数 + 并查集

P3294

C6　Trie 的 DFS 序：前缀约束变区间约束

P5840,P3311

C7　Trie + fail 树：多模式串计数

P5357,P2414

C8　多串最长公共子串

P5546,P2463

C9　在线 SAM + LCT

P5212

C10　SA + 关键点：求平方串

P1117

C11　字典序第 k 小后缀

P2408,P3975,P3809

C12　树上字符串问题：广义 SAM

P3346

20. 总结提升

20.1 全部结构的一句话本质

20.2 五条贯穿全书的主线

主线一：不重复读字符。 这是所有匹配算法的出发点。朴素匹配每次失配都从模式串头重来，浪费了"刚才比过的那一段"。哈希把整段压成一个数、KMP 把"已匹配长度"记成状态、Z 函数维护最右匹配段、Manacher 复用镜像半径——四者都在用"左边已算好的信息"避免重读。它们的复杂度论证也是同一个：某个指针单调推进，总推进量 O(n)。

主线二：子串 = 后缀的前缀。 这一句把 O(n^2) 个子串降成 n 个后缀，是 SA 与 SAM 的共同基础。SA 是"把后缀排序后逐个处理"，SAM 是"把后缀的前缀按 endpos 合并"。

主线三：四棵 fail 树是同构的。 KMP 的 fail 树、AC 自动机的 fail 树、SAM 的 parent 树、PAM 的 fail 树，都在做同一件事——把"后缀包含关系"编码成树上的祖先关系。于是 LCA、子树和、DFS 序 + 树状数组这几种工具全部通用。这是本书最值得记的一条。

主线四：所有状态数上界都来自"每次最多新增常数个"。 SAM 的状态数 \le 2n-1（每次 extend 最多 +2）、PAM 的节点数 \le n+2（每次最多 +1）、本质不同回文 \le n。这个摊还思想是压缩结构能 O(n) 的根本。

主线五：哈希 + 二分是万能备胎。 不想写 SA/SAM 时，O(\log n) 的 LCP 查询能解决大部分问题。只有需要"枚举全部子串"或"需要精确的 endpos 等价类"时才必须上自动机。

20.3 字符串题真正的难点在两处

第一处：转化。 P4287 的"双倍回文 = 回文 + 左半回文"、CF1200E 的"最大重叠 = KMP 停在末尾的 j"、P1117 的"AABB = 两个 AA 从中间拼起来"——把绕口的题面条件翻译成算法能回答的问题，这一步比写代码难得多。

第二处：选型。 同一个问题用哈希、KMP、Z 都能做，但代价与代码量差很多。§0.5 的决策表值得反复看——它的价值不在记住结论，而在养成"先问要什么，再选工具"的习惯。

20.4 已知边界与深入方向

本书未深入的内容：

• 后缀树的 O(n) 构造（Ukkonen）：只给了定义与性质。实战多用 SAM parent 树或 SA 替代。
• Main-Lorentz 的完整实现：只讲了思想与复杂度，未给完整代码。
• O(n) 后缀数组构造（SA-IS / DC3）：只讲了 O(n\log n) 的倍增法。SA-IS 在 n\ge10^6 且卡常时有用。
• Runs / 平方串计数：Lyndon 分解的理论延伸，本书只到"求全部平方串的位置"。
• 字符串与其他领域的交叉：如"字符串 + 网络流""字符串 + 计算几何"。