后缀树构造方法讲义

后缀树讲义1.基本定义后缀：一个长度为m的序列S=sss.....s，记S=ss.....s为S的第i个后缀，显123miii+1m然S1=S。后缀树：一个长度为m的序列S的后缀树是一个有根定向树，别且满足下面条件它刚好有m个叶节点。除了根节点之外的每一个内节点至少有两个子节点，并且每条边都对应S的一个非空子序列。任何从一个内节点出发的两条边对应的子序列的第一个字符都不同。每一条从根节点出发到叶子节点的路径对应序列S的一个后缀。第四个条件是后缀树的主要特征。6图1：序列xabxa$对应的后缀树路径的标签：我们称一个路径对应的序列叫路径的标签。一个节点的标签：从根节点到这个节点的路径对应的序列。注：并不是所有的序列都对应有后缀树，比如序列xabxa就没有后缀树因为后缀xa刚好是后缀xabxa的前缀，因此标签为序列xa的路径并不是叶节点，此时xabxa没有后缀树，为了解决这一问题，通常我们在序列末尾加上一个$字符（不同于序列中出现的任何字符）以解决这个问题，因为此时任何一个后缀都不可能是另外一个后缀的前缀。隐含后缀树：序列S的隐含后缀树指的是，序列S$的后缀树去掉那些有$的边上的$符号，然后将空白的边去掉得到的树。图2：xabxa的隐含后缀树。2.后缀树的构造后缀树的构造方法有很多种，其中Ukkonen’s算法是最容易理解的而且其时间和空间复杂度都是线性的，这里我们只讲这种算法。该算法根据S的前缀sss.....s构建一个隐含后缀树「，当I=m的时候r就是S的123iim后缀树，因此Ukkonen’s算法可以被分成m个阶段，在第I+1个阶段，根据「.构建树「工，而每一个阶段又被分成I+1个扩展，其中的第j个扩张确认S[j,j+1...I+1],1<j<i+1,即S[1—i]序列的第j个后缀在树中。算法过程如下：Ukkonen‘s后缀树构造算法构建后缀树r1I从1到m第I+1阶段开始j从1至到I+1开始｛第j个扩展｝在现在的已经构建好的树中找到从根节点出发的标签为Sj..i],如果需要的话将S[I+1]加到这条路径后面确认SU...I+1]在树中。第j个扩展结束。第I+1个阶段结束。后缀扩展规则令Sj..I]=p,p是S[1..i]的一个后缀，第j步扩展的主要任务是确保序列P,S[I+1]在树中规则1路径p是以一个叶子节点结束的，此时直接将S[I+1]加到叶子节点上面即可。规则2p后面没有路径以S[I+1]开始但是至少有一个路径是p的延续。此时如果p在一个内节点终止，则我们需要重新建一个叶子节点作为这个内节点的子节点并且它对应的路径标签是S[I+1]。当p是在一条边的中间的时候，此时除了建一个叶子节点之外还要建一个从根出发的标签为p的内节点。规则3有某个从p末端出发的路径是以S[I+1]开始的，此时我们什么也不用做。图3：axabxb的后缀树。上面算法的时间复杂度分析:一般情况下下，我们要花。(|时)的时间才能找到路径P，因此第I+1阶段的第j个扩展消耗时间是O(I+1-j)因此「,H可以经过O(i2)的时间从气扩展得到，因此构建[的时间复杂度是0(m3)。Ukknonen的算法是在这个简单算法的基础上，经过改进实现线性时间的。后缀链接：第一个加速技巧后缀链接：令^a为任意一个字符串，其中x为任意一个字符，a为任意一个字符串(可以为空)，对一个路径标签为xa的内节点v，如果有另外一个内节点s(v)的路径标签是a，那么一个从v指向s(v)的指针被称为后缀链接。命题1：如果一个新的路径标签xa为内节点v在第I+1个阶段的j个扩展中被加进树中，那么要么路径标签为a的内节点已经在树中存在，要么在第j+1个扩展中会出现。证明：内节点的出现只可能在扩展j实现的是规则二的时候，也就是说，此时路径xa后面有某个字符c而不是S[I+1]，因此在扩展j+1中肯定有一个路径的标签为a，但后面跟的是字符c。此时有两种情况，一种是a后面只有c字符，另外一种情况是a后面跟着其它字符。第二种情况s(v)节点肯定已经存在，第一种情况下，根据规则二，一个新的内节点s(v)将会被创建。故定理得证。推论：在Ukknonen算法中任何一个刚被创建得节点v到下一个扩展为止都将有一个后缀链接从它出发。为将S[j..i]扩展到Sj..I+1],重复下面得做法，从后缀树中路径S[j-1..i]的末端出发，我们最多移动一个节点到树的根节点或者是有后缀链接的内节点。令T是那条边的标签，如果v不是根节点，沿着后缀链接到S(v):然后沿着边的标签Y到路径S[j..i]的末尾，然后按照扩展规则完成由S[j..i]到S[j.I+1]的扩展。单步扩展算法(singleextensionalgorithm):SEA查找与S[j-1..i]对应的节点，或者是在该子串末端之上的那个节点v，要么节点有一个后缀链接，要么就是根节点，这就最多需要指针挪动一个位置。令y为v和S[j..i]的末端之间对应的路径。如果v不是根节点，指针转移到v的后缀链接S(v)上，然后沿着y对应的路径。如果v是根节点，直接查找S[j..i]对应的路径。根据扩展规则，确保S[j..i]S[I+1]在树中。如果在扩展j-1中出现一个新的内节点w，则根据定理必然有一个后缀链接从w指向S(W)o后缀链接的使用并没有降低运算复杂度。要降低复杂度，需要下面的技巧。技巧1:跳边技巧在第j+1个扩张中，沿着节点S(v)下一条标签为Y的路径，时间复杂度为Oy|.但是根据后缀树的定义，一个节点出发的几条路径开始的字符不可能相同，因此y的第一个字符必须是那条与y对应的边的第一个字符。令g'为这条边上的字符个数，g=y|，如果g'<g，我们可以跳过这条边，令g=g-g'，h=g'+1然后重复上面的过程，直到将y路径完全遍历为止。因此我们查找y的时间复杂度跟y的长度没有关系，而只和从这条路径上面的节点个数有关。深度：一个节点u的深度是从树根出发到这个节点的路径上面的所有节点的个数。命题2：如果(v,s(v))为一个后缀链接，则v的深度最多比S(v)的深度大1o证明：(略)，(根据后缀链接的定义)。定理：使用跳边技巧，算法的每一个阶段的时间复杂度都是O(m).证明：根据上面的算法实现过程，在单个扩展算法中，我们主要的操作就是从一个节点跳到另外一个节点，因此只要我们分析一下深度变化就可以了。单步扩展算法中向上最多跳一个节点，深度最多减少1，当沿着后缀链接跳的时候深度也是作多减一。因此在整个阶段当前节点的深度变化最多为2m次，而没有一个节点的深度可以超过m，故整个阶段的时间复杂度为O(m)o推论：利用后缀链接，Ukkonen算法的时间复杂度为O(m2)。后缀树的两个重要特征：如果一个节点是一个叶子节点，那么它将一直是一个叶子节点。(没有任何操作将一个叶子节点改为内节点的)规则3是一个停止规则。(一旦规则三实施，没有必要再查找下去)两个技巧：我们可以在常数时间内完成对叶子节点的扩张，用一个全局变量指向所有叶子节点的末尾。一旦规则三被使用，则这个阶段就结束了。单阶段算法(singlephasealg