算法导论：后缀树

算法导论：后缀树

参考资料：
在线构造后缀树
Ukkonen's Algorithm构造后缀树实录
后缀树系列
在阅读本文之前，需要了解字典树，请看字典树

定义：后缀树是一棵压缩字典树，其次，后缀树中存储的关键词为所有的后缀。

下面将对后缀树的构建以及优化做出详细的介绍。

1.后缀树的构建

1.1列出字符串所有后缀

以字符串S=MISSISSIPPI$为例
S的所有后缀如下：
S[0…11]= MISSISSIPPI$           字符串本身，起始位置0
S[1…11]=   ISSISSIPPI$            起始位置1
S[2…11]=  SSISSIPPI$            起始位置2
S[3…11]=    SISSIPPI$            起始位置3
   .
   .
S[10…11]=         I$           起始位置10
S[11…11]=        $            终结符
字符串最后的$是人为添加的，这样保证后缀的唯一性，不会出现横跨多个字符串的后缀。

1.2 在平方时间类构造后缀树

1.2.1 采用构建字典树方式构建（方法一）

（1）将上述字符串的所有后缀加入到字典树中，得到如下结构：

后缀树的构造

（2）将字典树中没有分支的路径压缩：

后缀树的构造
要遍历所有的结点时间复杂度为

1.2.2 多边同步插入构建（方法二）

这种方法的含义就是给定一个字符串，直接构造后缀树，不需要先构造字典树。
在讲这个方法之前，需要先了解一些概念：

基本概念

在这里后缀树中的结点分为两大类，显示结点，隐士结点。显示节点就是那些分支处或者叶子节点，隐式节点是被压缩的那些节点。还有用来辅助构造后缀树的尾部链表，构造时，会沿着尾部链表进行更新。

节点
沿着尾部链表更新时的规则：
我们通过例子来讲述这个更新规则，现在我们有字符串{ababcd$}，内部节点，叶子节点，隐式节点分别用不同的样式来表示。
构建后缀树

首先第一个字符a开始，构建如图所示，尾部链表从a的叶子节点指向根节点。现在我们插入下一个字符b，插入字符时说沿着链表进行更新的，这里先更新叶子节点，再更新根节点这个内部节点。

规则1
更新叶子节点时直接插入字符即可。
规则2
在更新到内部节点时的规则。
根据这两条规则，我们可以对字符串{ababcd$}的b字符进行更新。
构建后缀树
这里更新叶子节点时，将b直接放置在a后面即可，然后沿着链表更新根节点，因为紧邻着根节点的字符只有a，不存在b，所以构造出一个新的节点b出来。这样做的主要目的，就是希望表示出，字符的所有后缀，现在的后缀有两个ab和b，这两个字符都必须出现在后缀树上。尾部链表会指向新出现的节点，最后指向根节点。
下面我们沿着链表插入a，此时存在两个叶子节点，一个内部节点。
构建后缀树
沿着链表更新，首先更新最左边的节点，所以直接将字符a写后面即可。然后我们更新到右边的叶子节点，按照规则1也是直接写在后面。最后更新到根节点，紧靠着根节点的字符分别时左边的a和右边的b，根据规则2，我们不在构建新的节点，只是将左边a字符的节点做一个标记，因为现在的三个后缀是aba,ba,a，要在后缀树中全部体现出来。

现在插入字符b

构建后缀树
在沿着链表更新时，叶子节点以及内部节点按照规则即可，但是会遇到隐式节点，现在会有规则3
规则3
在按照规则的前提下，不断进行更新。
构建后缀树
构建完成后如下图所示，这种方法每一次都要从头开始遍历尾部链表
完成构建
后缀树与字典树的不同在于，它的边不再只代表单个字符，而是通过一对整数 [from, to] 来表示。其中 from 和 to 所指向的是字符串在文本中的位置，这样每个边可以表示任意的长度，
后缀树
以上就完成了后缀树的构建过程。
在使用方法二时，需要遵守的规则：

规则1：遇到叶子节点时只需往叶子所在的边上面的字符串后面插入字符就好了，不用改变树的结构；
规则2：遇到内部节点的时候，先看看插入的字符是否出现在显式节点后紧跟的字符
      集合中,如果插入的字符出现在集合中，那么什么也不要做（是指不用改变构），
      因为已经存在了；如果没有出现，在显式节点后面增加一个叶子，边上标注为这个字符。
规则3：遇到隐式节点时，先看看隐式节点后面的字符是不是当前将要插入的字符，
      如果有则不用管了，没有则需要将当前隐式节点变为显式节点，再增加新叶子。

2.优化后缀树的构建

是在方法二的基础上进行的优化，下面将哟用具体的例子进行讲解，给出的字符串为abcabxabcd$。

优化后方法

首先构建字符a

优化后方法
然后，依照之前的方法插入字符b,c。当我们插入下一个字符a的时候，会发现在后缀树中，存在字符a了。所以在这时，我们不能简单的插入。
优化后方法

我们在按规则插入之后，要在字符a后做一个标记，就像之前讲的隐式结点，表示出有由a开始的后缀，a之后的字符就可以在这里操作。
为了记录这些信息，我们需要引入一些概念：
1、活动点（active point)
是一个三元组(活动结点,活动边, 活动长度)
2、剩余后缀数（remainder）
还没有在后缀树中体现的后缀
  那对于上图，活动点是多少呢？答案是（0，a，1）0表示额就是根节点，在这个结点上进行活动。a表示的是会在由根节点周围a开始的那条边上进行相关操作，1表示的是在一位字符后操作，也就是a后，如果是2呢那就是在b后操作。
  此时还没有体现在后追树上的后缀数是1.也就是后缀a，因为我们并不能找到a这个后缀，我们只是在a后做了标记，表示接下来会有由a开始的标记。

优化后方法
插入字符b和上面的a类似。此时的剩余后缀有b,ab两个，活动长度也变为了2。当插入下一个字符x时，x并不在后缀树中，显然，我们应该做一些别的操作了。
此时，还没有体现在后缀树中的后缀有，{abx,bx,x}，此时我们要插入后缀abx
优化后方法
后缀abx出现在了后缀树上，还没有体现的后缀是bx,x。我们会发现图中的活动边变为了b，活动长度也减少了，这样是为了让剩下的后缀更好的插入。
规则1
在向根节点插入时，需要遵循规则1。
现在还剩下的后缀时bx,x依次插入。
优化后方法

此时活动点变为了（0（根节点），none(无活动边)，0(无长度)）,剩余的后缀是x。
我们会发现图中多了一条=由4指向6的索引。这个就是另一条规则。

规则2
这里的后缀连接类似于之前讲过的尾部链表，主要目的是为了节省插入时间，比如我们在插入ab开始的某个后缀后（例如abz），我们还需要插入bz，那就可以直接通过这个后缀连接插入b。
优化后方法
在插入x后如上图所示。
优化后方法
后面插入a,b,c因为这些字符都已经存在于后缀树里了，所以只需要做记录不需要操作，当我们插入到d时，这是一个新的字符，所以要处理所有的剩余后缀了，每当遇到新的字符，才会开始处理剩余后缀。
此时的记录信息为：
活动点(4,c,1)
剩余后缀为abcd、bcd、cd、d。此时先处理后缀abcd，我们在记录处按照规则插入d。
优化后方法
当我们处理完后缀abcd后，活动点变为了（6，c，1），活动结点直接从4变为了6，这个就是根据规则3来完成的。
规则3
优化后方法
在优化后方法中，需要遵守的三个规则：

规则1：当向根节点插入时遵循：
      活动点保持为 root； 
      活动边被设置为即将被插入的新后缀的首字符；
      活动长度减 1。
规则2：如果我们分裂一条边并且插入一个新的节点，并且，如果该新节点不是当前
      步骤中创建的第一个节点，则将先前插入的节点与该新节点通过一个特殊的指针 
      连接，称为后缀连接。后缀连接通过一条虚线来表示。
规则3：当从活动点不为根的节点分裂边时，我们沿着后缀连接的方向寻找节点，如
      果存在一个节点，则设置该节点为活动点；如果不存在，则设置活动点为根节点。活动边和活动长度保持不变。

在根据规则处理完所有的字符后，得到如图所示的后缀树，因为在整个过程中，只遍历了一遍字符串，且没有进行多余的结点操作，只是记录了一些信息，所以这个方法的时间复杂度是O(n)，可以在线性时间内完成。