后缀树

后缀树（suffix tree）是字符串索引结构，可视为一个字符串所有后缀组成的压缩字典树。普通字典树按字符逐层分支；后缀树把连续没有分叉的路径合成一条边，让边标签可以是一整段字符。从根沿标签走到某个叶子，就读出了对应的后缀。

通常先在原串末尾加一个此前未出现的终止符。以banana加上$为例，要组织banana$、anana$、nana$、ana$、na$、a$及$。独有终止符使一个后缀不会成为另一个后缀的真前缀，各个结束位置因而能明确落在叶子上，叶子再保存其在原串中的起点。

参考：[2]

压缩后，除特殊的根节点情形外，内部节点都必须发生分叉；叶子数与后缀数成正比，所以节点与边的数量为O(n)。但如果每条边都复制一份完整标签，字符串内容仍可能占用平方级空间，不能只数节点就宣布实现是线性的。

常用办法是保留原串，将边标签表示为原串中的起止下标。这样即使边上有很长的字符段，也只需常数个索引字段。这里的空间界通常以机器字计，索引需能容纳原串位置。先建出可能很大的未压缩后缀字典树再压缩，也不是线性时间构建法。

参考：[1]

模式P在原串中出现，当且仅当它是某个后缀的前缀。因此查询从根开始，按当前字符选择出边，再逐一比较边标签与剩余模式。中途字符不合或不存在相应出边，表示匹配失败；模式先耗尽则成功，即使它的末尾停在一条压缩边内部也一样。

例如在banana中查找ana，沿以a开始的路径匹配后，对应子树中的叶子给出起点1和3，这里下标从0计。查找anb则会在标签比较时遇到不一致。若出边选择为常数时间，长度m的模式存在性查询为O(m)，报告k次出现还须计入O(k)的输出成本。

参考：[2]

后缀链接等技术可复用相邻后缀的结构信息，避免每次从头重复插入。在固定大小字母表及适当算法与数据表示下，可以实现O(n)构建。若字母表很大、出边需平衡树查找，或使用哈希取得期望常数访问，相应的时间、空间与概率限定就应另行说明。

后缀数组把后缀起点按字典序放在数组中，通常更节省树指针等常数开销；后缀树则显式呈现公共前缀的分支结构，便于定位匹配子树以及分析重复片段。两者都索引同一文本，却不是相同布局。选择时应比较查询需求、构建成本和实际内存，而非把所有以树表示的字符串结构都叫后缀树。

参考：[1] [3]