OI-wiki 后缀树完全指南：定义、Ukkonen 线性构建算法与典型应用-开发者社区

OI-wiki 后缀树完全指南：定义、Ukkonen 线性构建算法与典型应用

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

后缀树（Suffix Tree）是 OI/ICPC 竞赛中处理字符串问题的一类重要数据结构：它将一个字符串的全部后缀组织进一棵压缩字典树，从而把"子串存在性、出现次数、最长公共前缀"等问题转化为树上路径与子树统计问题。本文以 OI-wiki 的后缀树文档为骨架，系统讲解后缀 trie 到后缀树的压缩过程、两种主流构建路线（反串 SAM 与 Ukkonen 算法）的源码实现，并结合仓库中的两道例题代码与测试数据，给出可直接运行验证的完整实战方案。读完本文，你将掌握后缀树的概念体系、$O(n)$ 构建的完整推导，以及用后缀树求解"子串出现次数乘长度最大值"与"循环同构串出现次数"两类典型问题的实现细节。

记号约定

记构建后缀树的母串为 $S$，长度为 $n$，字符集为 $\Sigma$：

$S[i]$ 表示 $S$ 中的第 $i$ 个字符，其中 $1 \le i \le n$；
$S[l, r]$ 表示 $S$ 中第 $l$ 个字符至第 $r$ 个字符组成的字符串，称为 $S$ 的一个子串；
$S[i, n]$ 为 $S$ 的以 $i$ 开头的后缀，$S[1, i]$ 为 $S$ 的以 $i$ 结尾的前缀。

这些记号贯穿全文所有算法与代码，尤其是区间 $[l,r]$ 表示法——Ukkonen 算法正是用它来 $O(1)$ 地描述树上一条边承载的字符串。

从后缀 trie 到后缀树：定义与节点数上界

后缀 trie：空间爆炸的朴素结构

定义字符串 $S$ 的后缀 trie为将 $S$ 的所有后缀插入至 trie 树中得到的字典树。在后缀 trie 中，节点 $x$ 对应的字符串为从根节点走到 $x$ 的路径上经过的字符拼接而成的字符串；记后缀 trie 中所有对应 $S$ 的某个后缀的节点为后缀节点。

后缀 trie 有一个非常优越的性质：它的非根节点恰好能接受 $S$ 的所有本质不同非空子串。也就是说，后缀 trie 天然就是"全体子串"的一个索引。然而代价同样显著——构建后缀 trie 的时空复杂度均为 $O(n^2)$，当 $n$ 达到 $10^5\sim 10^6$ 级别时完全不可接受，这正是引入后缀树的动机。

压缩出后缀树与隐式后缀树

压缩的关键是选取"关键点"：

令后缀 trie 中所有拥有多于一个儿子的节点和后缀节点为关键点，只保留关键点、把非关键点形成的链压缩成一条边，得到的压缩 trie 树即为后缀树（Suffix Tree）；
若只令后缀 trie 中所有拥有多于一个儿子的节点和叶结点为关键点，则得到隐式后缀树（Implicit Suffix Tree）。

容易看出，隐式后缀树是后缀树进一步压缩后得到的结果（后缀节点若没有分叉就继续被压掉）。

下图从左至右分别为以字符串 $\texttt{cabab}$ 为母串构建的后缀 trie、后缀树和隐式后缀树：

边的字符串与隐式后缀

在后缀树和隐式后缀树中，每条边对应一个字符串。每个非根节点 $x$ 对应了一个字符串集合：从根节点走到 $x$ 的父亲节点 $fa_x$ 经过的字符串，拼接上 $fa_x$ 至 $x$ 的树边对应的字符串的任意一个非空前缀，记为 $str_x$。同时，在隐式后缀树中，称一个没有对应任何节点的后缀为隐式后缀——这类后缀没有以叶结点形式显式出现，而是"藏"在某条边的内部。

节点数上界：至多 $2n$

考虑将 $S$ 的后缀逐个插入后缀 trie：从第二次插入开始，每次最多新增一个拥有多于一个儿子的节点和一个后缀节点，因此后缀树中节点个数最多为 $2n$ 个。线性大小的节点数，是后续 $O(n)$ 构建与 $O(n|\Sigma|)$ 遍历算法的前提，也使得后缀树可以直接用静态数组在代码中实现（见下文参考实现中大小为2 * N的节点池）。

后缀树的两种建立方式

方式一：反串建 SAM——支持前端动态添加字符

OI-wiki 文档给出了一个极具实用价值的结论：反串建 SAM 建出的 parent 树就是这个串的后缀树，因此只需把反串的字符逐个加入 SAM 即可离线构造后缀树。这与 SAM 文档中的论述一致：所有状态和所有后缀链接构成根为 $t_0$ 的根向树（后缀链接树，国内 OI 选手常称parent 树），且对字符串 $s$ 建立的后缀链接树与对其翻转 $s_R$ 建立的后缀树结构相同——这一性质常常用于离线构造后缀树。

参考实现（构建部分）如下，其extend即标准 SAM 的增量扩展，配合siz统计每个状态代表的 endpos 大小：

struct SuffixAutomaton { int tot, lst; int siz[N << 1]; int buc[N], id[N << 1]; struct Node { int len, link; int ch[26]; } st[N << 1]; SuffixAutomaton() : tot(1), lst(1) {} void extend(int ch) { int cur = ++tot, p = lst; lst = cur; siz[cur] = 1, st[cur].len = st[p].len + 1; for (; p && !st[p].ch[ch]; p = st[p].link) st[p].ch[ch] = cur; if (!p) st[cur].link = 1; else { int q = st[p].ch[ch]; if (st[q].len == st[p].len + 1) st[cur].link = q; else { int pp = ++tot; st[pp] = st[q]; st[pp].len = st[p].len + 1; st[cur].link = st[q].link = pp; for (; p && st[p].ch[ch] == q; p = st[p].link) st[p].ch[ch] = pp; } } } } SAM;

要点说明：

对 $S$ 的每个字符做extend即完成反串插入；由于 SAM 的 parent 树（后缀链接树）就是 $S$ 的后缀树，之后可以直接在这棵树上做子树统计、LCA 等操作。
这种路线天然支持"从串尾不断追加字符"的动态维护，代码实现短、不易出错，适合大多数 OI 场景。

方式二：Ukkonen 算法——支持后端动态添加字符

Ukkonen 算法是一种增量构造算法：依次向树中插入串 $S$ 的每一个字符，并在每次插入之后正确维护当前的后缀树。OI-wiki 文档先用一个朴素版本建立直觉，再引入后缀链接将其优化到 $O(n)$，以下完整继承这条推导主线。

朴素算法：以 $\texttt{abbbc}$ 为例

用字符串 $\texttt{abbbc}$ 演示构建过程。初始建立一个根节点，称为 $0$ 号节点；每条边维护一个区间 $[l,r]$ 表示这条边上的字符串为 $S[l,r]$；同时维护已经插入的字符个数 $m$（初始为 $0$）。

插入字符 $\texttt a$：从 $0$ 号节点伸出一条边 $[1,\infty]$ 指向新节点。这里的 $\infty$ 是一个极大值，可理解为"串的结尾"，这样插入新字符时，这条边会自动包含新字符。
插入字符 $\texttt b$：同样从 $0$ 伸出一条边 $[2,\infty]$。注意到之前延伸出的边 $[1,\infty]$ 的意义自动发生变化——随着串结尾的改变，其表示的串从 $\texttt a$ 变为 $\texttt{ab}$。这是正确的，因为此前所有后缀都已以叶节点形式出现在树中，只需向所有叶节点的末端插入当前字符。
再次插入字符 $\texttt b$：但 $\texttt b$ 已是之前插入字符串的一个子串，原树已经包含 $\texttt b$，此时什么都不做，记录一个 $k$ 表示 $S[k,m]$ 是当前最长的隐式后缀。
再插入一个 $\texttt b$：因为前一个 $\texttt b$ 没有插入成功，此时 $k=3$，要插入的后缀为 $\texttt{bb}$。从根向下寻找 $\texttt{bb}$，发现也在原树之中，仍然什么都不做。

这里有一个关键的不变量：如果 $S[k,m]$ 是隐式后缀，那么对于 $l>k$，$S[l,m]$ 都是隐式后缀。因为由 $S[k,m]$ 为隐式后缀可知，存在字符 $c$ 使得 $S[k,m]+c$ 为 $S$ 的子串，所以 $S[l,m]+c$ 也为 $S$ 的子串，由隐式后缀树的定义可知 $S[l,m]$ 也不作为叶结点出现。这正是我们只需要维护最长的隐式后缀、而无需逐个处理其余后缀的原因。

插入字符 $\texttt c$：此时 $k=3$，沿根向下寻找 $\texttt{bbc}$，发现不在原树中。我们需要在 $\texttt{bb}$ 对应的节点处延伸一条 $[5,\infty]$ 的出边——但该节点其实并不存在，而是包含在一条边的内部，因此需要分裂这条边：创建一个新节点，再在新节点处伸出生成的出边。此时插入成功，令 $k\to k+1$（因为 $S[k,m]$ 不再是隐式后缀）。
因为 $k$ 变化了，重复这个过程，直到再次出现隐式后缀，或 $k>m$（本例中是后者），构建过程结束。

朴素算法每次暴力从根向下寻找并插入，最坏复杂度为 $O(n)$，因此总复杂度为 $O(n^2)$。要优化，就必须解决"每次都要从根重新定位"这一瓶颈。

后缀链接（Suffix Link）：$O(1)$ 迁移插入位置

朴素算法慢，主要是因为每次 extend 都要从根找到最长隐式后缀的插入位置。为此引入二元组 $(now, rem)$ 来描述当前最长被隐式包含的后缀 $S[k,m]$：沿着节点 $now$ 的以 $S[m-rem+1]$ 开头的出边走长度 $rem$，到达的位置唯一表示一个字符串。每次插入新字符时，只需从 $(now, rem)$ 描述的位置查找。

当 $k\to k+1$ 时需要更新 $(now, rem)$：

如果 $now=0$，只需让 $rem \to rem-1$，因为下一个要插入的后缀是刚才插入的后缀去掉开头的 1 个字符；
否则，设 $str_{now}$ 对应的子串为 $S[l,r]$，需要找到一个节点 $now'$ 对应 $S[l+1,r]$，令 $now\to now'$。

引理：对隐式后缀树中任意非叶非根节点 $x$，树中存在另一非叶节点 $y$，使得 $str_y$ 是 $str_x$ 删去开头字符后的字符串。

证明：令 $s$ 表示 $str_x$ 删去开头字符形成的字符串。由隐式后缀树的定义可知，存在两个不同字符 $c_1,c_2$ 满足 $str_x+c_1$ 与 $str_x+c_2$ 均为 $S$ 的子串，因此 $s+c_1$ 与 $s+c_2$ 也为 $S$ 的子串，所以 $s$ 在后缀 trie 中也对应一个有分叉的关键点，即隐式后缀树中存在 $y$ 使得 $str_y=s$。∎

由该引理定义 $\operatorname{Link}(x)=y$，称为 $x$ 的后缀链接（Suffix Link），于是 $now'=\operatorname{Link}(now)$ 一定存在。因此我们只需要求出隐式后缀树中所有非根非叶节点的 $\operatorname{Link}$，即可实现插入位置的 $O(1)$ 迁移。

Ukkonen 算法主流程：两类情况与摊还分析

整体流程如下：为了构建隐式后缀树，从前往后加入 $S$ 中的字符。假设根节点为 $0$，当前已建出 $S[1,m]$ 的隐式后缀树且维护好了后缀链接，$S[1,m]$ 的最长隐式后缀为 $S[k,m]$，位置为 $(now,rem)$。设 $S[m+1]=x$，现在加入字符 $x$。此时 $S[1,m]$ 的每个后缀都需在末尾添加字符 $x$；由于所有显式后缀都对应叶结点、其父边右端点为 $\infty$，无需维护，所以只需考虑隐式后缀末尾添加 $x$ 对树形态的影响。先考虑 $S[k,m]$，分两种情况：

$(now,rem)$ 位置已经存在 $x$ 的转移：后缀树形态不变。因为 $S[k,m+1]$ 已出现在后缀树中，所以对 $l>k$，$S[l,m+1]$ 也会出现，只需 $rem\to rem+1$，不做任何修改。
$(now,rem)$ 不存在 $x$ 的转移：若 $(now,rem)$ 恰好是树中节点，则给该节点新增一条出边 $x$；否则需要分裂节点，在此位置新增一个节点并添加出边 $x$。此时对 $l>k$ 尚不清楚 $S[l,m]$ 的影响，还需继续考虑 $S[k+1,m]$：若 $now\ne 0$，利用后缀链接令 $now=\operatorname{Link}(now)$；否则令 $rem\to rem-1$。最后令 $k\to k+1$，重复上述过程。

每一步只消耗常数时间，算法在插入全部字符后停止，因此时间复杂度为 $O(n)$。

需要特别指出：Ukkonen 算法只能处理出 $S$ 的隐式后缀树，而隐式后缀树在某些问题中的功能不如后缀树强大，所以在需要时可以在 $S$ 末端添加一个从未出现过的字符，此时 $S$ 的所有后缀与树的所有叶子一一对应。这是两道例题代码中T.extend(0)这一步的由来。

参考实现（含边分裂与后缀链接维护）

以下为 OI-wiki 文档给出的 Ukkonen 算法参考实现，结构体字段含义如下：

ch[u][c]：节点 $u$ 的转移边，指向 $c$ 对应的子节点；
st[u]/len[u]：节点 $u$ 的父边承载的字符串在 $S$ 中的起始下标与长度；
link[u]：节点 $u$ 的后缀链接 $\operatorname{Link}(u)$；
now / rem / n：分别对应上文二元组 $(now,rem)$ 与当前串长 $m$；tot为节点总数，根节点编号为 $1$；
构造函数中len[0] = inf使"不存在转移"时ch[now][c]为空边的比较结果正确。

struct SuffixTree { int ch[M + 5][RNG + 1], st[M + 5], len[M + 5], link[M + 5]; int s[N + 5]; int now{1}, rem{0}, n{0}, tot{1}; SuffixTree() { len[0] = inf; } int new_node(int s, int le) { ++tot; st[tot] = s; len[tot] = le; return tot; } void extend(int x) { s[++n] = x; ++rem; for (int lst{1}; rem;) { while (rem > len[ch[now][s[n - rem + 1]]]) rem -= len[now = ch[now][s[n - rem + 1]]]; int &v{ch[now][s[n - rem + 1]]}, c{s[st[v] + rem - 1]}; if (!v || x == c) { lst = link[lst] = now; if (!v) v = new_node(n, inf); else break; } else { int u{new_node(st[v], rem - 1)}; ch[u][c] = v; ch[u][x] = new_node(n, inf); st[v] += rem - 1; len[v] -= rem - 1; lst = link[lst] = v = u; } if (now == 1) --rem; else now = link[now]; } } } Tree;

代码中的几个关键细节：

第 1 个while循环实现"从 $(now,rem)$ 沿边下降"：只要剩余长度大于当前出边的长度，就整条边跳过并下移节点，这是 $O(1)$ 摊还的关键。
if (!v || x == c)对应主流程情况 1（转移已存在则直接break；否则创建新叶子节点）。
else分支对应情况 2的边分裂：新建内部节点u承接原来的子节点v，再为字符x创建新的叶子，同时把v的父边缩短rem-1个字符（st[v] += rem - 1; len[v] -= rem - 1;）。
lst = link[lst] = ...统一维护本轮新建/经过节点的后缀链接，最后依据now是否为根决定--rem还是now = link[now]，正好对应 $S[k+1,m]$ 的位置迁移。

后缀树的作用：为什么它是"字符串万能树"

后缀树的价值在于树上路径与子串的一一对应：后缀树上每一个节点到根的路径都是 $S$ 的一个非空子串，这在处理很多字符串问题时都很有用。更进一步的结论构成它与后缀数组、后缀自动机之间的桥梁：

后缀树的 DFS 序就是后缀数组（对应后缀数组文档中的 $sa$ 数组）；
后缀树的一个子树对应后缀数组上的一个区间；
后缀树上两个后缀的最长公共前缀是它们对应叶节点的 LCA，因此后缀数组 height 数组的结论可以理解为：树上若干节点的 LCA 等于 DFS 序最小和最大的节点的 LCA。

这意味着：子串出现次数（子树叶子计数）、本质不同子串数（路径长度统计）、任意两后缀的 LCP（LCA 深度）等经典问题，都可以在后缀树上统一、直观地解决。

例题一：P3804【模板】后缀自动机（SAM）——子树叶子统计

题意：给定一个只包含小写字母的字符串 $S$，求出 $S$ 的所有出现次数不为 $1$ 的子串的"出现次数 × 子串长度"的最大值。

解法：建出插入一个终止符的隐式后缀树。树上每条从根出发的路径都构成子串；一个显式后缀的出现次数即对应节点子树内的叶子节点个数。隐式后缀无需考虑，因为一个隐式后缀的出现次数等于向下走到的第一个节点对应显式后缀的出现次数，且一定没有该显式后缀长。所以遍历整棵树，求出每个节点子树内叶子个数与每个节点到根的路径长度，若叶子个数 $>1$ 则更新答案。复杂度 $O(|S||\Sigma|)$。

完整参考代码见 docs/string/code/suffix-tree/suffix-tree_1.cpp，其核心统计函数如下：

pair<long long, int> search(int u, int dep = 0) { if (st[u] + len[u] >= n) return {0, 1}; // 叶子：终止符边，贡献 1 个显式后缀 dep += len[u]; long long ans{0}; int ys{0}; for (int i{0}; i <= RNG; ++i) if (ch[u][i]) { auto res = search(ch[u][i], dep); ans = max(ans, res.first); ys += res.second; // 子树内叶子总数 = 出现次数 } if (ys > 1) ans = max(ans, 1LL * dep * ys); return {ans, ys}; }

主函数中先对每个字符T.extend(s[i] - 'a' + 1)，再T.extend(0)插入终止符（字符0不在原串中出现，保证后缀与叶子一一对应），最后T.search(1)从根开始统计。仓库测试数据 suffix-tree_1.in 为abab，对应答案 suffix-tree_1.ans 为4：子串ab出现 2 次、长度为 2，乘积最大为 $2\times 2=4$，与"出现次数不为 1 的子串"条件吻合。

例题二：CF235C Cyclical Quest——循环同构的在线匹配

题意：给定小写字母主串 $S$ 和 $n$ 个询问串，求每个询问串 $x_i$ 的所有循环同构在主串中出现的次数总和（同一循环同构重复出现只计一次）。

解法：建立插入终止符的隐式后缀树。枚举当前循环节，记录在树上能匹配到多长的前缀：重复类似 Ukkonen 算法的过程，记录当前匹配位置 $(now,rem)$，每次尝试插入下一个字符，成功则继续、失败则跳出循环。若某次成功匹配了当前循环节且该循环节之前没出现过，则更新答案。切换到下一个循环节时，要删去当前匹配子串开头的字符——这正好相当于令 $now\to\operatorname{Link}(now)$；若 $now=1$ 则直接 $rem\to rem-1$。复杂度 $O(|S||\Sigma|+\sum|x_i|)$。

完整参考代码见 docs/string/code/suffix-tree/suffix-tree_2.cpp。代码中：

init(u)自底向上累加每个内部节点子树内的叶子数cnt[u]，即该节点代表子串的出现次数；
test(t, m)对长度为 $m$ 的询问串，把串复制成t + t模拟所有循环同构，用(now, rem)维护当前匹配位置，vis[...] != time保证同一循环同构（对应到树中同一节点）只统计一次，从而正确去重；
切换循环节时的if (now == 1) --rem; else now = link[now];与 Ukkonen 构建中的位置迁移完全同构。

仓库测试数据 suffix-tree_2.in 给出主串baabaabaaa与 5 个询问串a, ba, baa, aabaa, aaba，对应答案 suffix-tree_2.ans 为7 5 7 3 5，可作为实现正确性的直接验证。

小结：三条路线的选型建议

构建方式	复杂度	动态能力	适用场景
后缀 trie（朴素）	$O(n^2)$ 时空	支持	仅用于理解概念，无法处理大数据
反串建 SAM（parent 树）	$O(n	\Sigma	)$	支持从尾部追加字符	实现简洁，OI 竞赛中最常用
Ukkonen 算法	$O(n)$ 摊还	在线、逐个字符扩展	需要在线维护或理解最坏线性算法的场景

后缀树把"所有子串"压缩进一棵 $O(n)$ 节点的树中，节点上天然的子树统计、LCA、DFS 序等结构，使其与后缀数组、后缀自动机互相印证、互相转化。建议读者在掌握概念与推导后，配合本文给出的两份完整参考代码与测试样例实际运行验证，再通过 SAM 文档与后缀数组文档对比三者之间的关系，即可建立起完整的字符串后缀结构知识体系。