后缀树是一种数据结构，一个具有m个字符的字符串s的后缀树T,就是一个包含一个根节点的有向树，该树恰好带有m+1个叶子（包含空字符），这些叶子被赋予从0到m的标号。每一个内部节点，除了根节点以外，都至少有两个子节点，而且每条边都用S的一个子串来标识。出自同一节点的任意两条边的标识不会以相同的字符开始。 后缀树的关键特征是：对于任何叶子i，从根节点到该叶子所经历的边的所有标识串联起来后恰好可以拼出S的从i位置开始的后缀，即S[i,…,m]。
后缀树（后缀Trie）最早由Weiner在1973年引⼊。McCreight在1976年⼤幅简化了后缀树的构造算法。他的⽅法从右向左构造后缀树,由于是从末端开始构造，因此限制为离线算法。1995年，Ukkonen给出了第⼀个从左向右的on-line构造算法。这三种⽅法都是线性时间算法（ O(n) 时间），近来的研究发现，它们彼此之间有着紧密的联系。
1） 对任意给定字符串S,建立其后缀树； 2） 查找一个字符串S是否包含子串T； 3） 统计S中出现T的次数； 4） 找出S中最长的重复子串。所谓重复子串是指出现了两次以上的子串； 5） 分析以上各个算法的时间复杂性
- Ukkonen方法详解 https://www.oschina.net/translate/ukkonens-suffix-tree-algorithm-in-plain-english
- 源代码Java版：https://blog.csdn.net/vickyway/article/details/50059095
本代码对原构造代码进行了修改，用C++写出来，但仍有部分bug，暂时搁置，暂时发现的bug有：hcuhuccuhshcu$uchshuccuhuch#、abacabdabcdacad等