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$ 没有插入成功此时 $k3$要插入的后缀为 $\texttt{bb}$。从根向下寻找 $\texttt{bb}$发现也在原树之中仍然什么都不做。这里有一个关键的不变量如果 $S[k,m]$ 是隐式后缀那么对于 $lk$$S[l,m]$ 都是隐式后缀。因为由 $S[k,m]$ 为隐式后缀可知存在字符 $c$ 使得 $S[k,m]c$ 为 $S$ 的子串所以 $S[l,m]c$ 也为 $S$ 的子串由隐式后缀树的定义可知 $S[l,m]$ 也不作为叶结点出现。这正是我们只需要维护最长的隐式后缀、而无需逐个处理其余后缀的原因。插入字符 $\texttt c$此时 $k3$沿根向下寻找 $\texttt{bbc}$发现不在原树中。我们需要在 $\texttt{bb}$ 对应的节点处延伸一条 $[5,\infty]$ 的出边——但该节点其实并不存在而是包含在一条边的内部因此需要分裂这条边创建一个新节点再在新节点处伸出生成的出边。此时插入成功令 $k\to k1$因为 $S[k,m]$ 不再是隐式后缀。因为 $k$ 变化了重复这个过程直到再次出现隐式后缀或 $km$本例中是后者构建过程结束。朴素算法每次暴力从根向下寻找并插入最坏复杂度为 $O(n)$因此总复杂度为 $O(n^2)$。要优化就必须解决每次都要从根重新定位这一瓶颈。后缀链接Suffix Link$O(1)$ 迁移插入位置朴素算法慢主要是因为每次 extend 都要从根找到最长隐式后缀的插入位置。为此引入二元组 $(now, rem)$ 来描述当前最长被隐式包含的后缀 $S[k,m]$沿着节点 $now$ 的以 $S[m-rem1]$ 开头的出边走长度 $rem$到达的位置唯一表示一个字符串。每次插入新字符时只需从 $(now, rem)$ 描述的位置查找。当 $k\to k1$ 时需要更新 $(now, rem)$如果 $now0$只需让 $rem \to rem-1$因为下一个要插入的后缀是刚才插入的后缀去掉开头的 1 个字符否则设 $str_{now}$ 对应的子串为 $S[l,r]$需要找到一个节点 $now$ 对应 $S[l1,r]$令 $now\to now$。引理对隐式后缀树中任意非叶非根节点 $x$树中存在另一非叶节点 $y$使得 $str_y$ 是 $str_x$ 删去开头字符后的字符串。证明令 $s$ 表示 $str_x$ 删去开头字符形成的字符串。由隐式后缀树的定义可知存在两个不同字符 $c_1,c_2$ 满足 $str_xc_1$ 与 $str_xc_2$ 均为 $S$ 的子串因此 $sc_1$ 与 $sc_2$ 也为 $S$ 的子串所以 $s$ 在后缀 trie 中也对应一个有分叉的关键点即隐式后缀树中存在 $y$ 使得 $str_ys$。∎由该引理定义 $\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[m1]x$现在加入字符 $x$。此时 $S[1,m]$ 的每个后缀都需在末尾添加字符 $x$由于所有显式后缀都对应叶结点、其父边右端点为 $\infty$无需维护所以只需考虑隐式后缀末尾添加 $x$ 对树形态的影响。先考虑 $S[k,m]$分两种情况$(now,rem)$ 位置已经存在 $x$ 的转移后缀树形态不变。因为 $S[k,m1]$ 已出现在后缀树中所以对 $lk$$S[l,m1]$ 也会出现只需 $rem\to rem1$不做任何修改。$(now,rem)$ 不存在 $x$ 的转移若 $(now,rem)$ 恰好是树中节点则给该节点新增一条出边 $x$否则需要分裂节点在此位置新增一个节点并添加出边 $x$。此时对 $lk$ 尚不清楚 $S[l,m]$ 的影响还需继续考虑 $S[k1,m]$若 $now\ne 0$利用后缀链接令 $now\operatorname{Link}(now)$否则令 $rem\to rem-1$。最后令 $k\to k1$重复上述过程。每一步只消耗常数时间算法在插入全部字符后停止因此时间复杂度为 $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[k1,m]$ 的位置迁移。后缀树的作用为什么它是字符串万能树后缀树的价值在于树上路径与子串的一一对应后缀树上每一个节点到根的路径都是 $S$ 的一个非空子串这在处理很多字符串问题时都很有用。更进一步的结论构成它与后缀数组、后缀自动机之间的桥梁后缀树的 DFS 序就是后缀数组对应 后缀数组文档 中的 $sa$ 数组后缀树的一个子树对应后缀数组上的一个区间后缀树上两个后缀的最长公共前缀是它们对应叶节点的 LCA因此后缀数组 height 数组的结论可以理解为树上若干节点的 LCA 等于 DFS 序最小和最大的节点的 LCA。这意味着子串出现次数子树叶子计数、本质不同子串数路径长度统计、任意两后缀的 LCPLCA 深度等经典问题都可以在后缀树上统一、直观地解决。例题一P3804【模板】后缀自动机SAM——子树叶子统计题意给定一个只包含小写字母的字符串 $S$求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数 × 子串长度的最大值。解法建出插入一个终止符的隐式后缀树。树上每条从根出发的路径都构成子串一个显式后缀的出现次数即对应节点子树内的叶子节点个数。隐式后缀无需考虑因为一个隐式后缀的出现次数等于向下走到的第一个节点对应显式后缀的出现次数且一定没有该显式后缀长。所以遍历整棵树求出每个节点子树内叶子个数与每个节点到根的路径长度若叶子个数 $1$ 则更新答案。复杂度 $O(|S||\Sigma|)$。完整参考代码见 docs/string/code/suffix-tree/suffix-tree_1.cpp其核心统计函数如下pairlong 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 24$与出现次数不为 1 的子串条件吻合。例题二CF235C Cyclical Quest——循环同构的在线匹配题意给定小写字母主串 $S$ 和 $n$ 个询问串求每个询问串 $x_i$ 的所有循环同构在主串中出现的次数总和同一循环同构重复出现只计一次。解法建立插入终止符的隐式后缀树。枚举当前循环节记录在树上能匹配到多长的前缀重复类似 Ukkonen 算法的过程记录当前匹配位置 $(now,rem)$每次尝试插入下一个字符成功则继续、失败则跳出循环。若某次成功匹配了当前循环节且该循环节之前没出现过则更新答案。切换到下一个循环节时要删去当前匹配子串开头的字符——这正好相当于令 $now\to\operatorname{Link}(now)$若 $now1$ 则直接 $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)$ 时空支持仅用于理解概念无法处理大数据反串建 SAMparent 树$O(n\Sigma)$支持从尾部追加字符实现简洁OI 竞赛中最常用Ukkonen 算法$O(n)$ 摊还在线、逐个字符扩展需要在线维护或理解最坏线性算法的场景后缀树把所有子串压缩进一棵 $O(n)$ 节点的树中节点上天然的子树统计、LCA、DFS 序等结构使其与后缀数组、后缀自动机互相印证、互相转化。建议读者在掌握概念与推导后配合本文给出的两份完整参考代码与测试样例实际运行验证再通过 SAM 文档 与 后缀数组文档 对比三者之间的关系即可建立起完整的字符串后缀结构知识体系。延伸阅读本文主要参考 2021 年国家集训队论文《后缀树的构建》代晨昕以及 EternalAlexander 的《炫酷后缀树魔术》一文感兴趣的读者可在此基础上进一步研究后缀树的线性时间构建细节与更多应用。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考