后缀树的用途，总结起来大概有如下几种 :
1. 查找字符串o是否在字符串S中
方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。
原理：若o在S中，则o必然是S的某个后缀的前缀。
听起来有点拗口，举个例子。例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀。有了这个前提，采用trie搜索的方法就不难理解了。
2. 指定字符串T在字符串S中的重复次数
方案：用S+'$'构造后缀树，搜索T节点下的叶节点数目即为重复次数 。
原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。
3. 字符串S中的最长重复子串
方案：原理同2，具体做法就是找到最深的非叶节点。
这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。
4. 两个字符串S1，S2的最长公共部分
方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。大体原理同3。
///////////////////////////////////////////////////////////
后缀树的存储：为了节省空间，我们不在边上存储字符串，而是存储该字符串在原串中的起止位置，空间复杂度O(n)。
后缀树的构造：最简单的方法，使用Trie的构造方法，时间复杂度为O(n^2);
后缀树也可以在O(n)的时间复杂度内构造，但比较复杂。
如，基本思路：先向后缀树中插入最长的后缀串(S本身)，其次插入次长的后缀串，以此类推，最后插入空串。定义后缀链接(Suffix Link)=从节点A指向节点B的指针，B所表示的子串是A所表示的子串的最长后缀。既，根节点到A所经过的字符串s=aw，则从根节点到B所经过的字符串为w。
算法所用符号描述：
后缀树的构造，算法流程：
1)定义SL(root)=root，首先插入S，此时后缀树仅有两个节点。
2)设已经插入了S(i),现在要插入S(i+1)，分两种情况讨论：
1：P(S(i))在插入之前已经存在，(如，na，ana，a是na的parent)，则P(S(i))有后缀链接，令u=SL(P(S(i)))，从u开始沿着树往下查找，在合适的地方插入。
2：P(S(i))是插入S(i)过程中产生的，此时G(S(i))必定存在并有后缀链接，比如(na，ana，bana)，令u=SL(G(S(i)))，w=W(G(S(i)),P(S(i))).从u开始，对w进行快速定位， 在合适的地方插入新的节点。
不断重复以上步骤，即可完成后缀树的构造。