后缀树

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

单词BANANA的后缀树。$为终止符。从根到叶的六条路径（方框里）对应六个后缀：A$、NA$、ANA$、NANA$、ANANA$和BANANA$。叶子中的数字表示出现的起点位置。后缀链用点线画出

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