————《高级数据结构》
技巧一：
每条边维护对应字串的长度（一下简计为边的长度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次方)，不过似乎又回到了最初朴素算法的时间复杂度，下面我们将其进行进一步的优化。

进一步的加速
我们在扩展过程中还发现了如下规律：
规律1：在第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意味着树的结构不会改变，所以没有必要继续扩展了。
这条规律显然能够降低运行时间，不过其具体效果还甚不明朗。
规律2：如果一个节点为叶节点，那么再整个算法运行过程中，它将一直是叶节点。
对叶节点的修改仅会再扩展规则1中出现，而规则1对叶节点的修改只是将其父亲边的标记延申，所以叶节点始终为叶节点。这样我们再具体实现的时候如果新建的是叶节点，就可以对所有的叶节点父亲边的标记位置统一结束为止，所以修改叶节点只许哟啊O（1）的时间。
技巧3：如果用ji 表示第i阶段最后一次应用规则1或者规则2的扩展，那么有ji<=jI+1,也就是说，第i+1阶段的扩展可以直接从上一次的最后位置ji开始。
简要证明如下：根据规则2，在第i阶中从扩展1到扩展ji不是更新叶节点就是创造叶节点，因此，在第i+1阶段的扩展1到扩展ji-1都是对叶节点进行扩展。所以可以直接从扩展ji开始，而所有对叶节点的扩展由上可知可以在常数时间内完成。
综上所述，应用技巧2（扩展终止条件）和技巧3（扩展位置不降），再加上之前的后缀链加速，我们可以在线性时间内完成所有隐式树的构建！(简要证明：由于序列ji单调不降，所以总的扩展次数为j1+j2-j1+j3-j2+1…+jm-jm-1+1<=2m-1)，又由后缀链加速可知，其时间复杂度为O（m）。
我们还有最后一个步骤——通过在最后以可隐式树Tm来构建我们的后缀树。由于我们要构建的后缀树是S <math> <semantics> <mrow> <mi mathvariant="normal"> 的 </mi> <mi mathvariant="normal"> 后 </mi> <mi mathvariant="normal"> 缀 </mi> <mi mathvariant="normal"> 树 </mi> <mi mathvariant="normal"> ， </mi> <mi mathvariant="normal"> 所 </mi> <mi mathvariant="normal"> 以 </mi> <mi mathvariant="normal"> 在 </mi> <mi mathvariant="normal"> 这 </mi> <mi mathvariant="normal"> 最 </mi> <mi mathvariant="normal"> 后 </mi> <mi mathvariant="normal"> 一 </mi> <mi mathvariant="normal"> 步 </mi> <mi mathvariant="normal"> ， </mi> <mi mathvariant="normal"> 我 </mi> <mi mathvariant="normal"> 们 </mi> <mi mathvariant="normal"> 将 </mi> <mi> S </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> 的后缀树，所以在这最后一步，我们将S </annotation> </semantics> </math>的后缀树，所以在这最后一步，我们将S看作一个整体再进行一次扩展，将所欲以是S$结尾的后缀添加到树中，总的时间复杂度不变。至此，我们完成了后缀树线性时间构造算法的介绍。