后缀树

维基百科,自由的百科全书
跳转至: 导航搜索
单词BANANA的后缀树。$为终止符。从根到叶的六条路径(方框里)对应六个后缀:A$NA$ANA$NANA$ANANA$BANANA$。叶子中的数字表示出现的起点位置. 后缀链用点线画出

后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀樹的概念最早由Weiner 於1973年提出,既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改進完善。

一个string S 的后缀树是一个边(edge)被标记为字符串的树.因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径.这样就形成了一个S的后缀的基数树(radix tree). 后缀树是前缀树(trie)里的一个特殊类型.