什么是后缀树？

说到后缀树，我相信很多人通过名字看出来树是一种结构形态，后缀树就是带后缀的结构，后缀，顾名思义，甚至通俗点来说，就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1≤i≤n，子串SiSi+1...Sn便都是字符串S的后缀。当然这样只是通过文字形式上的理解，不够全面，下面我们来看看具体的定义和表现形式吧。

什么是后缀树？

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

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

后缀树的定义：长度为m的序列S，其后缀树是一个有向树，满足以下条件：

（1）有m个叶结点； 

（2）除了根结点和叶结点，每一个内部结点至少有两条边（子节点），每条边对应S中的一个非空序列；

（3）从任何一个内部结点出发的两条边对应的字符串序列的第一个字符都不相同；

（4）从根结点到叶结点的路径上的字符序列构成了S从i开始的一个后缀字符串；

路径标签：一个路径上对应的字符序列称为路径标签；

结点标签：从根结点开始到此结点对应的路径的标签称为结点标签；

并不是所有的字符序列都有后缀树，例如xabxa（其后缀有xabxa，abxa，bxa，xa，a）xa为xabxa的前缀，为了解决此问题，通常在字符串末尾加上$符号，使得任何一个后缀都不为其他后缀的前缀。

 注：从根结点到叶子结点路径上的字符（词）表示对应叶节点 i 开始的某一个后缀字符串，叶子结点存储了起始位置 i 有几个字符（词）就有几个叶子结点，根结点和内部结点不存储任何数据，只有叶子结点和边存储数据；

虽然本篇的文字内容不是很多，但是却用最直观的形式进行讲解，不知道大家看完后，有没有形成一套知识体系呢？