后缀树

结构与查询 ​

对 (T$) 的 (n+1) 个后缀建立压缩Trie公理库字典树Trie · Prefix tree按字符串前缀共享路径组织键集合的树形数据结构。。每个叶对应一个后缀起点，内部节点至少两子；边标签不复制字符串，只存 (T[l..r))，故节点与空间 (O(n))。模式 (P) 沿边逐字符匹配，到达 locus 后其叶子即出现位置。

文本 banana$ 的 ana$ 与 anana$ 共享 ana 前缀，压缩后是一条边而非三个单字符节点。若复制每条边标签，总长度可能 $\mathrm{\Theta }(n^2)$，线性节点数救不了空间。

终止符与边界 ​

唯一且字典序最小的终止符让任何后缀都不是另一后缀的前缀，并固定独立叶。Suffix link 连接 (aX) 与 (X) 的内部状态，用于线性构造，但查询正确性不依赖具体构建算法。

后缀树是显式拓扑索引；suffix array 是叶的字典序线性化，suffix automaton识别子串语言。三者空间与接口不同。

线性构建通常假设常数字母表，或假设子边字典能在线性总成本内处理；一般有序字母表可能多出对数因子。构建时间、导航时间与报告输出是三个不同成本坐标。

构造对象与边表示 ​

叶 $i$ 代表后缀 $T[i..n]\mathrm{\$}$，边只存二元组 $(l,r)$ 指向原文本 $T[l..r)$。内部节点的字符串深度是根到它的边长总和；边中途的位置是 implicit node，不额外分配对象。压缩后每内部节点至少两孩子，因此内部节点少于叶，节点总数小于 $2n+2$。

对 banana$，根的 a 子树共享 ana 前缀，叶起点 1 与 3 在 ana 后分叉。若把 ana 分别复制到多条边，所有后缀边标签总长度会回到 $\mathrm{\Theta }(n^2)$；区间引用是线性空间证明的必要部分。

模式查询逐步执行 ​

查询 ana：从根按 a 找边，逐字符比较边标签；模式若在边中途耗尽，该隐式 locus 下全部叶都是出现位置，得到 1、3。若边上第二字符失配，立即无解。每个模式字符只消费一次，所以导航字符工作 $O(|P|)$，枚举叶另付 $O(occ)$。

子边若用数组且字母表常数，选择为 $O(1)$；有序 map 则每节点多 $O(\log |\mathrm{\Sigma }|)$。不能无条件把搜索写成 $O(|P|)$。

Suffix link 与近邻索引 ​

Suffix link 从路径标签 $aX$ 的内部节点指向 $X$，让在线构造复用上一后缀的匹配状态；它不改变后缀树定义，也不是查询必须跟随的边。Suffix array只保存叶的字典序，空间更紧但模式搜索需二分/LCP；suffix automaton 压缩的是所有子串的右端等价类，节点语义不同。

参考资料

• Edward McCreight, “A Space-Economical Suffix Tree Construction,” JACM, 1976.
• Esko Ukkonen, “On-line Construction of Suffix Trees,” Algorithmica, 1995.