后缀树(Suffix Tree)

定义

后缀树(Suffix Tree)是把一个字符串的所有后缀插入压缩字典树(每条边代表一段子串而非单字符)得到的树形结构,通常在串尾添加不出现的终止符以保证每个后缀对应一个叶子。

构造

Weiner 于 1973 年首先给出线性时间构造算法,McCreight 随后简化,Ukkonen 于 1995 年提出的在线算法最为著名,可以在 O(n) 时间内边读入字符边增量构建,依赖后缀链接(suffix link)避免重复遍历。

应用

后缀树可在 O(m) 时间判断长度为 m 的模式串是否为子串;还能高效求最长重复子串、两串的最长公共子串、回文相关问题,在基因组分析、抄袭检测、数据压缩中都有应用。

优缺点

优点是功能强、查询快、理论性质优美;缺点是空间常数大(每个节点需存多个指针),实现复杂,工程中常被后缀数组或后缀自动机替代。