Suffix tree：把所有后缀叠成一棵树
Trie 一页把一组 word 的前缀共享成树。同样的构造换到后缀上：取一段 text 的全部后缀插进一棵 Trie，得到 suffix trie。它能回答关于 text 的各种子串问题——因为「pattern 是 text 的子串」⟺「pattern 是某个后缀的前缀」⟺「pattern 是这棵树里从 root 出发的一条路径」。再把树里所有单链压缩成一条带子串的边，就是紧凑的 suffix tree。
哨兵 $:给 text 末尾补一个不出现在别处的字符 $，可保证没有任何后缀是另一个后缀的前缀，于是每个后缀都干净地落在一个叶子上，叶子里记它的起始下标。下面所有树都建在 text + $ 上。
1 · 第一步：插入全部后缀 → suffix trie
text 末尾补哨兵 $ 后，把全部后缀逐个插入（和 Trie 一页的构建完全一样，只是这次插的是后缀）。叶子上的虚线环表示「一个后缀在此结束」。
2 · 第二步：压缩单链 → suffix tree，沿边查子串
把每条「只有一个孩子」的链坍缩成一条边、边上写整段子串，树的节点数立刻缩小（内部节点都是分叉点，叶子标后缀起点）。查子串就从 root 选首字符匹配的边，沿边的子串逐字符核对——可能停在边中间。走完 pattern = 命中；命中点子树下所有叶子的下标，就是 pattern 的全部出现位置。
**能力与代价：**建好后，「pattern 是否子串」O(m)、「出现几次 / 都在哪」「最长重复子串」「最长公共子串」都能在树上高效回答。代价是构建——朴素插入是 O(n²);Ukkonen 算法能在线性时间建出同一棵树，只是过程复杂，不在本页展开。它和 suffix array 是同一信息的两种形态，可互相转换。