后缀树的应用

    ——————《高级数据结构》
    在这一节中，我们将给出几个常见的后缀树的应用，并且你将会看到它与其他处理字符串的算法与数据结构（例如KMP算法，AC自动机等）之间的比较。后缀树是一个非常强大的处理字符串问题的工具，并且企图在这一节短篇幅里面穷尽其应用是不可能的。因此，这里的介绍旨在抛砖引玉，更多的应用可以参考相关的书籍以及该领域的最新研究成果。
   字符串的精确匹配

情形一:
给定两个串S和T，分别代表模式串和文本串，长度分别为n和m，现在需要在串T中查找串P的每一个出现的位置。
了解KMP算法的读者一定对这个问题非常熟悉——这正是KMP算法应用的经典场景。在比较两者之前我们先看一下后缀树的算法实现。。
后缀树实现：首先构建串T的后缀树，所用时间复杂度为O(m),然后我们只需要在后缀树中查找串S即可。如果串S没有出现在后缀树中，那么显然串T不包含串S；如果串S结束于后缀树的某个节点v（结束于某一条边内的情形也类似），那么节点v的路径标记在T中出现的每个位置都匹配串S。为了知道所有出现的位置，我们只需要遍历v的子树，找到所有叶节点，便可以知道所有对应位置出现的位置了。当然，我们还有优化的余地——如果我们能够较快的找到v的字数中所有叶节点的话，就能够将查询降到O(n+k)，其中k为S在T中出现的次数，也就是节点v子树中叶节点的个数，这正是一个于KMP一样优秀的时间复杂度。实现方式也很简单，将叶节点按照便利顺序额外用链表依次连接，每个内部节点只需标记叶节点的范围即可（肯定是连续的一段）。
伪代码：
Function FindMatches(S)
{
v<-FindNode(S) //找到深度最小的节点v，使得S是v的路径标记的前缀
if (Exist(v)) Then
For i<-FirstLeaf(v) to LastLeaf(v) do
PrintLocation(i) //找到该后缀对应的起始位置
End For
End If
}
那么后缀树于KMP算法相比处理这类问题有何优势呢？如果对于文章确定不变，而模式串有多个的情形，KMP算法对于每次查询，都需要先花费O(n)的时间构建模式串的pi数组，然后再花费O(n)的时间去匹配，所以单次查询就需要花费O（n+m）的时间，而后缀树可以依次花费O(m)的时间构建文章串的后缀树，然后每次查询都只需要花费O(n+k)的时间。

 二：给定文章串T和模式集合S，串T长度为m,集合S中串长度为n，现在需要知道每个模式串在文章串T中的出现情况。
 该情形是对情形一的扩展，用AC自动机可以获得与kmp类似的时间复杂度，为O（n+m）。后缀树的实现与情形一类似，花费O(m)的时间构建树，然后每次查询对每个串注意执行情形一的算法，查询总时间为O(n).可见，后缀树处理这样的扩展情形也非常方便。
 三：
 给定长度为n的模式串S，现在需要处理若干次询问，每次询问将给出一个长度为m的文章穿T，询问S在每个T中出现的位置。
 还记得情形一中提到的后缀树会由于KMP算法的情况吗？情形三恰好与这种情况相反，所以KMP算法有者有优异的表现—只需要花O（n）的时间对模式串S预处理，每次查询花费O（m）的时间。如果用后缀树，每次花费O（n）的时间预处理，然后再花费O（n）的时间查询的话，该算法就没有KMP优秀了。那么，如何改进使得后缀树在这种情形下也可以表现的和KMP一样优秀呢？
 后缀树实现：对于文章串T，我们构建一个长度为m的数组ms。其中ms（i）表示T的后缀i所能够匹配的S的最长长度（无论何处开始的子串）。例如T=abcd，S=babc，那么ms（1）=3.显然如果串S出现在串T中等价于存在这样的i，使得ms（i）=n.
 我们现在来讨论如何计算出ms数组。首先，花费O（n)的时间构建串S 的后缀树。计算ms（1）,我们只需要用朴素的方法——即当做T匹配S，在S中查找T直到找到串T或者找到第一个没有办法匹配的位置，这样就计算出了ms（1）.计算ms（2）的时候，我们从T的第二个字符开始查找，回想后缀树的构建过程，这正相当于扩展的情形！当时我们使用后缀链加速，所以在这里我们同样应用后缀链快速计算ms数组。
 具体的说，假设计算ms（1）的时候最后到达了节点v，那么下一次，我们从节点v的后缀链指向的节点u开始计算ms（2）根据后缀链的定义，v的路径标记匹配字符串T[1..m]的前缀，那么u的路径标记匹配字符串T[2..m]的前缀，所以算法正确性得以保证。类似于之前关于时间复杂度的证明，我们这里可以直接得出结论——计算ms数组的时间复杂度为O(m)。
 要找到所有匹配的位置也很简单，找出那些满足ms（i）=n的i即可。这样，在这种情形下，我们用后缀树实现了不劣于KMP的算法的时间复杂度的算法。
 伪代码：
 function findmatches(T)
 activeNode<-root//初始化被激活的节点
for i<-1 to m do
 v<-godown(activeNode,T,i) //从激活节点开始向下走到不能走为止
 Calculate(v,ms(i))//根据终止位置计算ms(i)
 if (ms(i)==n)
   Then print(i)
 End If
 if (!nsideAnEdge) Then //如果终止于节点v
 activeNode<-suffixLink(v)
 Else activeNode<-SuffixLink(u)
End If 
End For


四：
给定一个字符串集合T。接下来你需要面对这样一个问题：每次给定一个字符串S，询问该字符串是集合T中哪些字符串的字串。
注意该问题与情形二的区别——情形二每次询问那些字符串是询问字符串的子串，而这里刚好相反，询问哪些字符串包含询问串，所以我们来看后缀树如何解决。
后缀树实现：假设集合T中字符串总长度为,m,我们花费O（m）的时间来构建T中所有字符串的广义后缀树。接下来的方法类似情形一了——在该后缀树中查找串S。如果找到了串S对应的位置，则该位置的子树中所有叶节点上的所有字符串都包含串S，我们可以用类似情形一的方法找到所有出现的位置，时间复杂度为O（n+k）,其中k为S在集合T中出现的总次数；如果没有找到这样的位置，那么显然S不是T中任何一个字符串的子串。
可见，情形四是对情形一的扩展——其效率是非常优秀的——仅仅和读入这些字符串所需要的时间相当。另外我们也看到了广义后缀树的方便之处，从情形四到情形一，我们甚至不用改变代码！

公共子串问题
情形五
给定两个字符串S1和S2.求这两个字符串的最长公共子串（注意区别于最长公共子序列）。
这个经典问题可以用朴素的动态规划在O(n*m)的时间复杂度内求解，当然我们并不满足于这样的效率，所以来看一下后缀树有怎样的表现。
后缀树实现：构建S1和S2的广义后缀树，这样会花费线性时间O(n+m).对于后缀树中每个节点v，如果在以v为根的子树中存在标记为S1的后缀的叶节点，则给v标记上1；类似的，如果子树中存在标记为S2的后缀的叶节点，则给v标记上2.如果节点v既有标记1又有标记2，那么v的路径标记就是S1和S2的公共子串。我们不加证明的给出最长公共子串满足的条件——该子串是同时标记上1和2的某个节点v的路径标记，并且这个节点v所有满足同时有两种标记的节点中字符深度最大的节点（即v的路径标记最长）。
给每个节点 标记，我们只需要通过对后缀树执行依次深度优先便利即可。因此总的时间复杂度为O(n+m)，这个效率已经非常优秀了。
function travel(v)
mask<-tag(v)
for I<-firstchild(v) to lastchild(v) do
travel(i)
mask<-mask or tag(i)
end for
if (mask==3)
then updateanswer(v)
end if
tag(v)<-mask
优化：还记得情形三中我们是怎样处理的吗？——引入数组ms。在这里我们这样使用：ms是一个长度为n的数组，ms(i)代表S1的后缀i与S2的某个子串的最长公共前缀。显然，其中ms(i)的最大值即S1与S2的最长公共子串的长度。用这种方法的好处是节省了空间——我们仅需建立字符串S2的后缀树，空间复杂度从o(n+m)降到了O（m）。