Suffix tree：把所有后缀叠成一棵树

Trie 一页把一组 word 的前缀共享成树。同样的构造换到后缀上：取一段 text 的全部后缀插进一棵 Trie，得到 suffix trie。它能回答关于 text 的各种子串问题——因为「pattern 是 text 的子串」⟺「pattern 是某个后缀的前缀」⟺「pattern 是这棵树里从 root 出发的一条路径」。再把树里所有单链压缩成一条带子串的边，就是紧凑的 suffix tree。

1 · 第一步：插入全部后缀 → suffix trie

text 末尾补哨兵 $ 后，把全部后缀逐个插入（和 Trie 一页的构建完全一样，只是这次插的是后缀）。叶子上的虚线环表示「一个后缀在此结束」。

2 · 单链压缩与沿边查询

把每条「只有一个孩子」的链坍缩成一条边、边上写整段子串，树的节点数立刻缩小（内部节点都是分叉点，叶子标后缀起点）。查子串就从 root 选首字符匹配的边，沿边的子串逐字符核对——可能停在边中间。走完 pattern = 命中；命中点子树下所有叶子的下标，就是 pattern 的全部出现位置。