后缀树链表实现板子

由后缀树构建隐式树，划分i阶段
回顾
1.
ukkonen的算法的伪代码
function buildplicitTree()
{Build TreeT1;
for i<-1 to m-1 do //处理阶段i+1
for j<-1 to i+1 do//处理第j次扩展
在当前树中找到字符串S[j…i]对应的位置，然后看是否需要添加字符S[i+1]
}
规则1：串S[j…i]终止于叶节点，也就是说从根节点到该叶节点的路径标记为串S[j…i]，此时只需要将该叶结点的父边的操作最后加上字符S[i+1]即可。
规则2：串S[j…i]对应的位置不是叶节点，（可能是中间节点，也可能是某条边的内部位置，因为一条可以代表某个子串），同时，串S[j…i+1]又不在当前树中，那么我们需要将该树进行扩展——如果 S[j…i]对用的位置在边内部，那么需要将该边在该位置处拆开，然后添加进新的节点，这样保证了S[j…i]终止与一个节点；然后新建一个该节点的子节点，然新建一个该节点的子节点（一个新的叶子节点），其间的边标记为S[i+1].
规则3：串S[j…i+1]已经在树中找到，那么我们不需要做任何修改。

后缀链加速
下面，我们引入后缀链，并结合一个小技巧来优化上述算法，其中a为单个字符串，其中a为单个字符，而b可以是包括空串在内的任意字符串。在隐式树中，如果一个节点v的路径标记对应ap，而节点s(v)对应标记p，那么我们建立从v指向s(v)的后缀链。特别是如果p为空串，那么有从v到根节点的后缀链。根节点没有后缀链。
如何将后缀链应用于加速。
在上面的朴素算法中的第i+1阶段第j次扩展的时候，需要花费O(m)的时间定位串S[j…i]对应的位置，一下我们通过研究第1次和第2次扩展来看后缀链如何优化这一步。
在第i+1阶段的第1次扩展中时，容易知道S[1…i]一定是终止于叶节点，因为它是前缀S[1…i]的最长后缀。所以在这次扩展中，我们很容易就找到位置（只需要维护一个指针记录最长后缀对应叶节点即可），然后应用1规则扩展。
在第2次扩展中，我们需要找到S[2…i]对应的位置。我们从第1次扩展的叶节点向上走到其父节点。如果v是根节点，那么下一步就沿着根节点向下走查找串S[2…i]，就像朴素算法一样；如果v是内部节点，那么我们沿着其后缀链找到其指向的节点s(v)，此时，s(v)的路径标记为S[2…i]的前缀S[2…k],2<=k<=i，所以我们找到其根节点s(v),然后再像朴素算法那样继续向下走，即在s(v)为根的子树中查找串S[k+1…i]对应的位置。
之后的第3次扩展直到第i+1次扩展与上述过程类似。不过，此时的算法时间复杂度并没有被优化，因为我们沿着后缀链向上走后，仍然需要向下走来找到对应串的位置，其时间复杂度仍然为O(m).不过不用担心，我们可以应用下面的一些小技巧来优化。

技巧1：每条边维护对应的字串的长度（以下简计为边的长度Length（edge））。回想后缀树的定义（这里是隐式树），”从同一个节点引出的任意两条边上标的字符串都不会以相同字符开始“，所以我们只需要知道引出边的第一个字符就知道”往哪里走了“。而该边的其他字符我们并不需要一个一个检验，只需要比对边的字串长度与当前要往下走的字符个数即可。过程描述如下：
（1）.当前要走往下走的字符个数为C，那么我们可以根据引出边的第一个字符找到”往哪里走“，假设沿着边e走，如果Length（e）<C,那么转（2），否则可以在O（1）的时间内找到对应的位置，终止。
（2）沿着边e走到底，并且把C置为C-Length(e)，转（1）.
也就是说，现在向下走所需要的时间复杂度为O（向下走的节点个数），而不是O（向下走的字符个数）。现在的时间复杂度似乎不容易看出，不过我们先给出如下命题：任意节点v的深度至多比其后缀链指向节点s(v)的深度大1.
 有了以上命题，我们可以得到第i+1阶段所有扩展总的时间复杂度为O(m)。简要证明：每次扩展，我们会向上走一个节点，然后找到该节点后缀链指向节点（如果需要），所以至多向上走两个节点。总的向下走的节点个数<=每次向上走的节点个数+当前树深度，故第i+1个阶段所有扩展的时间复杂度仍为O（m）.
 通过后缀链加速，我们将总时间复杂度优化到了O（m的2次方），不过似乎又回到了最初朴素算法的时间复杂度，下面进一步优化。
 4.进一步加速
    我们在扩展过程中还发现了如下的几条规律。
    规律一：在第i+1个阶段中，如果某一次扩展满足了扩展规则3，那么该阶段之后的扩展都没有必要了。
    简要证明：如果在第j次扩展满足了规则3，那么就意味着S[j..i+1]已经在树中了，于是我们会发现S[j+1..i+1],S[j+2,..i+1],..S[i+1..i+1]都在树中，而满足规律3，意味着树的结构不会改变，所以没有必要继续扩展了。