后缀树 | Codeboy's Blog

形式陈述

构造对象

设原文本为

T=T[0..n)\in\Sigma^n,\qquad n\ge1,

取一个不属于字母表的唯一终止符 $\$\notin\Sigma$ ，并令

S=T\$, \qquad N=|S|=n+1.

后缀树是 $N$ 个后缀

S[i..N), \qquad 0\le i<N,

所形成Trie的路径压缩版本：把所有内部度为 1 的非根路径压成一条边。终止符只需在原文本中从未出现，就能保证没有一个后缀是另一个后缀的前缀，因此每个后缀都对应独立叶。把终止符再约定为字典序最小，只是为了让后缀排序顺序更方便，并不是“后缀都成为叶”的必要条件。

每条边标签是 $S$ 的某个非空子串，但实现不复制字符，而只存一对半开区间端点 $(l,r)$ ，表示 $S[l..r)$ 。叶 $i$ 记录后缀起点 $i$ 。每个内部节点（包括根）都至少有两个孩子；因此 $N$ 个叶对应至多 $N-1$ 个内部节点，节点总数至多 $2N-1=2n+1$ ，连同边区间和子指针占 $O(n)$ 个机器字，假定字符编码、下标和指针各占常数个字。空文本可单独看作只含终止符的退化实例，不影响渐近结论。

模式查询

给定不含终止符的模式 $P$ ，从根按首字符选择边，并沿边引用的文本区间逐字符比较。若全部字符匹配，模式终止位置可能是显式节点，也可能位于一条压缩边中间；这个位置称为 locus。locus 下方所有叶的起点，恰好是 $P$ 在 $T$ 中的出现位置。

字符比较至多消费 $|P|$ 个模式字符。若每个节点能在 $O(1)$ 时间按首字符选边，查询导航为 $O(|P|+1)$ ，再用 $O(\mathrm{occ})$ 时间报告全部出现。空模式的 locus 为根，报告原文全部 $n+1$ 个边界。若子边保存在有序映射中，选择一条边通常需要 $O(\log(|\Sigma|+1))$ ，还须把这项字母表查找成本乘入导航步数。

直觉

朴素后缀 Trie 同时存放 $N$ 条总长度为 $\Theta(n^2)$ 的后缀。后缀树的线性空间来自两次压缩：没有分叉意义的单子路径被折叠成一条长边，长边的字符又只用原文本区间引用。只做到前一项而复制全部边标签，最坏空间仍会回到平方级。

终止符把“某个后缀恰好在内部节点结束”的情况显式推到叶上。它不是为了参与普通模式匹配，而是给每条后缀一个独一无二的结尾，使后缀起点、叶和报告位置形成一一对应。

例子与边界

对 banana$ 采用 0 起点编号。后缀 1 是 anana$，后缀 3 是 ana$，二者共享前缀 ana，随后分别沿 n... 与 $ 分叉。压缩结构只保留这次真正分叉；这里还存在后缀 a$，所以根后的 a 已是一次分叉，ana 的路径实际分成 a 与 na 两条边；各边分别引用原串区间，不复制字符。

查询 ana 时，先沿 a 边，再沿 na 边，到达显式分叉节点，其下叶 1 和 3 都被报告。查询 an 则在 na 边中间结束，仍报告同一组叶。这同时展示了显式与隐式 locus。若第二个字符已经失配，则立即返回空结果，不需要检查其他后缀。

终止符必须是新字符。若直接对不带终止符的 aaaa 建压缩 Trie，短后缀会在长后缀路径的内部结束，叶与后缀不再天然一一对应，算法和节点计数就必须额外维护 terminal 标记。允许这种“隐式后缀树”并非错误，但它是另一套表示约定，不能与显式终止符版本混写。

显式节点、隐式位置与 suffix link

根到显式节点的拼接标签称为该节点的 path label，其长度是字符串深度。压缩边中间的位置是 implicit locus，不需要分配节点，却仍可成为模式匹配的终点。

若某个非根内部节点的 path label 为 $aX$ ，其中 $a$ 是首字符，suffix link 指向 path label 为 $X$ 的显式节点；当 $X$ 为空串时目标就是根。它让 McCreight、Ukkonen 等构造复用前一个后缀的匹配信息，从而避免从根反复扫描；suffix link 属于构建加速结构，不是后缀树定义或静态查询正确性的前提。

线性时间构建还依赖字母表模型。常数字母表、整数字母表或可在线性总成本内维护的子边字典可以达到 $O(n)$ ；一般比较字母表上的平衡树导航可能引入对数因子。构建时间、模式导航时间和输出报告时间应分别陈述。

推论与应用

后缀树可在线性空间内支持子串存在性、出现位置报告、最长重复子串和多文本公共子串等任务。许多应用在树节点上再维护字符串深度、叶区间、最低公共祖先或文档颜色信息；这些是建立在拓扑索引之上的附加层，不应混入后缀树的基本定义。

Suffix array保存后缀的字典序排列，是后缀树叶序的线性化，通常更紧凑但查询依赖二分、LCP 或额外索引。Suffix automaton压缩的是子串的右端等价类，把全部状态设为接受时识别子串语言；它的状态不对应后缀树节点，二者不能仅因都能做子串查询而视为同一种结构。

参考资料

Peter Weiner, “Linear Pattern Matching Algorithms,” 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1–11.
Edward M. McCreight, “A Space-Economical Suffix Tree Construction Algorithm,” Journal of the ACM 23(2), 1976, pp. 262–272.
Esko Ukkonen, “On-line Construction of Suffix Trees,” Algorithmica 14, 1995, pp. 249–260.
Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, Chapters 5–7.

形式陈述 ​

构造对象 ​

模式查询 ​

显式节点、隐式位置与 suffix link ​

反向链接

形式陈述

构造对象

模式查询

显式节点、隐式位置与 suffix link