文档介绍：后缀树讲义
后缀:一个长度为m的序列,记为S的第i个后缀,显然=S。
后缀树:一个长度为m的序列S的后缀树是一个有根定向树,别且满足下面条件
它刚好有m个叶节点。
除了根节点之外的每一个内节点至少有两个子节点,并且每条边都对应S的一个非空子序列。
任何从一个内节点出发的两条边对应的子序列的第一个字符都不同。
每一条从根节点出发到叶子节点的路径对应序列S的一个后缀。
第四个条件是后缀树的主要特征。
图1:序列xabxa$对应的后缀树
路径的标签:我们称一个路径对应的序列叫路径的标签。
一个节点的标签:从根节点到这个节点的路径对应的序列。
注:并不是所有的序列都对应有后缀树,比如序列xabxa就没有后缀树因为后缀xa刚好是后缀xabxa的前缀,因此标签为序列xa的路径并不是叶节点,此时xabxa没有后缀树,为了解决这一问题,通常我们在序列末尾加上一个$字符(不同于序列中出现的任何字符)以解决这个问题,因为此时任何一个后缀都不可能是另外一个后缀的前缀。
隐含后缀树:序列S的隐含后缀树指的是,序列S$的后缀树去掉那些有$的边上的$符号,然后将空白的边去掉得到的树。
图2:xabxa的隐含后缀树。
后缀树的构造方法有很多种,其中Ukkonen’s算法是最容易理解的而且其时间和空间复杂度都是线性的,这里我们只讲这种算法。
该算法根据S的前缀构建一个隐含后缀树,当I=m的时候就是S的后缀树,因此Ukkonen’s算法可以被分成m个阶段,在第I+1个阶段,根据构建树,而每一个阶段又被分成I+1个扩展,其中的第j个扩张确认S[j,j+1…I+1],,即序列的第j个后缀在树中。算法过程如下:
Ukkonen‘s后缀树构造算法
构建后缀树
I从1到m
第I+1阶段开始
j从1到I+1
开始{第j个扩展}
在现在的已经构建好的树中找到从根节点出发的标签为S[j…i],如果需要的话将S[I+1]加到这条路径后面确认S[j…I+1]在树中。
第j个扩展结束。
第I+1个阶段结束。
后缀扩展规则
令S[j…I]=, 是S[1..i]的一个后缀,第j步扩展的主要任务是确保序列,S[I+1]在树中
规则1路径是以一个叶子节点结束的,此时直接将S[I+1]加到叶子节点上面即可。
规则2后面没有路径以S[I+1]开始但是至少有一个路径是的延续。此时如果在一个内节点终止,则我们需要重新建一个叶子节点作为这个内节点的子节点并且它对应的路径标签是S[I+1]。当是在一条边的中间的时候,此时除了建一个叶子节点之外还要建一个从根出发的标签为的内节点。
规则3有某个从末端出发的路径是以S[I+1]开始的,此时我们什么也不用做。
图3:axabxb的后缀树。
上面算法的时间复杂度分析:
一般情况下下,我们要花的时间才能找到路径,因此第I+1阶段的第j个扩展消耗时间是O (I+1-j)因此可以经过O()的时间从扩展得到,因此构建的时间复杂度是O()。Ukknonen的算法是在这个简单算法的基础上,经过改进实现线性时间的。
后缀链接:第一个加速技巧
后缀链接:令为任意一个字符串,其中x为任意一个字符,为任意一个字符串(可以为空),对一个路径标签为的内节点v,如果有另外一个内节点s(