精华内容
下载资源
问答
  • 后缀树 构建算法

    2019-04-05 01:08:20
    NULL 博文链接:https://ytrgmj.iteye.com/blog/1513687
  • 后缀树 后缀树的实现。 如何运行: > ghci suffixTree.hs λ graph . SuffixTree.construct $ "cacao" (或您想要的任何其他字符串而不是“ cacao ”) 依赖关系 ( brew install graphviz ) ( cabal install ...
  • 后缀树代码

    2017-08-20 21:57:33
    后缀树及其相关功能(如找最大子串等),参考https://www.oschina.net/translate/ukkonens-suffix-tree-algorithm-in-plain-english网站的UKKonen算法讲解(较易理解)与...abacabdabcdacad等
  • 后缀树

    2019-03-09 13:01:06
    1、后缀树的定义 后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出,既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。 后缀,...

    1、后缀树的定义

    后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出,既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。

    后缀,顾名思义,甚至通俗点来说,就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn,和整数i,1 <= i <= n,子串SiSi+1...Sn便都是字符串S的后缀。

    以字符串S=MISSISSIPPI为例,它的长度为11,所以S[1..11], S[2..11], ... , S[11..11]都算S的后缀,我们一般还把空字串也算成后缀。这样,我们一共有如下后缀。对于后缀S[i..n],我们说这项后缀起始于i。

    S[1..11], MISSISSIPPI
    S[2..11],    ISSISSIPPI
    S[3..11],     SSISSIPPI
    S[4..11],       SISSIPPI
    S[5..11],          ISSIPPI
    S[6..11],           SSIPPI
    S[7..11],             SIPPI
    S[8..11],               IPPI
    S[9..11],                PPI
    S[10..11],                PI
    S[11..11],                   I
    空字串,记为$。

      而将这些后缀全部插入前面提到的trie树中并压缩,就得到后缀树啦

    5046078640_1c523b50175045455851_ec8ec3410e

    两种方法在平方时间内构件后缀树

      所谓的平方时间是指O(|T|*|T|),|T|是指字符串的长度。

      第一种方法非常显然,就是直接按照后缀树的定义来就可以了,将各个后缀依次插入trie树中,再压缩,总的时间复杂度显然是平方级别的。

      这里给出的是另外一种方法。对照上面MISSISSIPPI的所有后缀,我们注意到第一种方法就是从左到右扫描完一个后缀再从上到下扫描所有的后缀。那么另外一种思路就是,先安位对齐,然后从上到下扫描完每个位,再从左到右扫描下一位。举个例子吧,第一种方法相当于先扫描完后缀1:MISSISSIPPI ,再往下扫描后缀2:ISSISSIPPI 以此类推;而第二种方法相当于从上到下先插入第一个字符M,然后再从上到下插入第二个字符I(有两个),然后再从上到下插入字符S(有三个)以此类推,参见下图。

    QQ截图20131221093315

    但是具体怎么操作呢?因为显然每次操作不能是简简单单的插入字符而已!

      我们再后头来看看上述过程,形式化一点,我们将原先的字符串表示为

      T = t1t2 … tn$,其中ti表示第i个字符

      Pi = t1t2 … ti , i:th prefix of T

      那么,我们每次插入字符ti,相当于完成一个从Trie(Pi-1)到Trie(Pi)的过程,当所有字符插入完毕的时候我们整个后缀树也就构建出来了。参见下图:插入第二个字符b相当于完成了从Trie(a)到Trie(ab)的过程。。。

    QQ截图20131221094705

      那我们怎么做呢?

    上图中也提示了,其实我们需要额外保留一个尾部链表,连接着当前的“尾部”节点--也就是对应着Pi的一个后缀的那些个点。我们注意到尾部链表实际上是从表示T[0 .. i]后缀的点指向表示T[1 .. i]后缀的点再指向表示T[2 .. i]后缀的点,以此类推

    也可以看得出来,每次插入一个字符都需要遍历一下链表,第一次遍历的时候链表长度为1(就是根节点),第二次遍历的时候链表长度为2(点a,和根节点,参见Trie(a) ),以此类推,可知遍历的总复杂度是O(|T|*|T|),建立链表也需要O(|T|*|T|),后续压缩Trie也需要O(|T|*|T|),故而整个算法复杂度就是O(|T|*|T|)。

    现在说明一下为什么算法是正确的?Trie(Pi-1)存储的是Pi-1的所有后缀,Trie(Pi)存储的是Pi的所有后缀。Pi的后缀可以由Pi-1所有后缀后面插入字符ti,以及后缀ti所构成。那么我们沿着Trie(Pi-1)尾部链表插入字符ti的过程也就是插入Pi的所有后缀的过程,所有算法是正确的。

    但是,有没有小失望,毕竟干了这么久发现跟第一种方法相比没有收益)。

    其实不用失望,我们做这么多的目的在于通过改进,整个算法可以实现线性的,下面就一步步介绍这种改进算法。

    改进第二种算法以实现线性时间建立后缀树

    首先一点我们必须直接在后缀树上操作了,不能先建立Trie树再压缩,因为遍历Trie树的复杂度就已经是平方级别了。

      我们定义几种节点:

    •   叶节点:   出现在后缀树叶子上的节点;
    •   显式节点:所有出现在后缀树中的节点。显然叶节点也是显示节点;
    •   内部节点:显示节点中不是叶子节点的所有节点;
    •   隐式节点:出现在Trie树中但是没有出现在后缀树中的点;(因为路径压缩)

    5046078486_397fb08303

     

      接下来我们来看看前面提到的尾部链表,尾部链表显然包含了当前后缀树中的叶节点以及部分的显式/隐式节点。沿着尾部链表更新:

    • 遇到叶子节点时只需往叶子所在的边上面的字符串后面插入字符就好了,不用改变树的结构;
    • 遇到显式节点的时候,先看看插入的字符是否出现在显式节点后紧跟的字符集合中(比如上图中红色的显式节点后紧跟的字符集和就是{s,p}),如果插入的字符出现在集合中,那么什么也不要做(是指不用改变树的结构),因为已经存在了;如果没有出现,在显式节点后面增加一个叶子,边上标注为这个字符。
    • 遇到隐式节点时,一样,先看看隐式节点后面的字符是不是当前将要插入的字符,如果有则不用管了,没有则需要将当前隐式节点变为显式节点,再增加新叶子。

      我们用个例子来说明一下怎么操作,为了便于说明隐式节点,我采用Trie树表示:

    QQ截图20131221103813 QQ截图20131221105514

    从第三个图到第四个图,沿着尾部链表插入字符a,那么链表第一个节点为叶节点,故而直接在边上插入这个字符就好了;链表第二个节点还是叶子,在边上插入字符就好了;第三个节点是隐式节点,看看紧跟着隐式节点后面的字符,不是a,故而将这个隐式节点变为显式节点,再增加一个叶子;第四个是显式节点(根节点),其紧跟的字符集和为{a,b},a出现在这个集合中,故而不用改变结构了。当然了,链表还是要维护的啊,O(∩_∩)O哈哈~

    好了,到此,我们实现了直接在后缀树上操作而完全撇开Trie树了,小有进步啦,~\(≧▽≦)/~啦啦啦,现在开始优化啦!

    自动更新叶节点

    首先一点,在后缀树上直接操作的时候,边上的字符串就没必要直接存储啦,我们可以存这个字符串对于在原先总的字符串T中的坐标。如上方右边那个图就是将左边第四个图,压缩之后得到的后缀树。[2,4]就表示baa。

    这样一来啊,存储后缀树的空间就大大减小了。

    接着,我们来看一下啊,后缀树S(Pi-1)中的叶子节点在S(Pi)中也是叶子节点,也就是说”一朝为叶,终身为叶“。而且我们还可以注意到尾部链表的前半部分全是叶子。也就是说如果S(Pi)有k个叶子,那么表示T[0 .. i],……,T[k-1 .. i]后缀的点全是叶子。

    我们首先来看一下什么时候后缀会不在叶子上:T[j .. i-1]不在S(Pi-1)叶子上,表明代表该后缀的点之后还有点存在,也就是说T[0 .. i-1]中存在子串S=T[j .. i-1] + c’ ,其中c’不为空。注意一下这是充分必要条件,因为叶子节点后面是不可能还存在点的。

      现在我们来证明一下:(ti加入到 S(Pi-1) 的过程)

    • 首先,T[0 .. i-1]肯定在叶子上。为什么呢,因为在S(Pi-1)中T[0 .. i-1]是最长的,如果它不在叶子上,那么必然存在比T[0 - i-1]还长的串,矛盾,故而T[0 .. i-1]一定在叶子上。
    • 其次,对于任何 j < i-1, 如果 T[j .. i-1] 不在树叶上,那么 T[j+1 .. i-1] 更不可能在树叶上;为什么呢,因为T[j .. i-1]不在叶子上表明T[0 .. i-1]中存在子串S=T[j .. i-1] + c’ ,其中c’不为空。那么T[0 .. i-1]中y也必然存在子串S‘=T[j+1 .. i-1] + c’,因为S’是S的后缀。故而 T[j+1 .. i-1]也不在叶子上
    • 于是我们知道k个叶子一定是T[0 .. i],……,T[k-1 .. i]

    我们来利用一下上述性质。叶节点每次更新都是把ti插入到叶子所在边的后缀字符串中,所以表示字符串的区间就变成了[ , i]。那么我们还有必要每次都沿着尾部链表去更新么?

    我们可以这样,将叶子那个边上的表示字符串的区间用[ , #]来表示,#表示当前插入字符在T中的下标。那么这样一来,叶子节点就自动更新啦。

    再利用第二个性质,我们完全就可以不管尾部链表的前k个节点啦

    这是又一大进步!

    当新后缀出现在原先后缀树中

    我们来看,根据沿尾部链表更新的算法,无论是显式节点还是隐式节点,当带插入字符ti出现在节点的紧跟字符集合的时候,我们就不用管了。也就是说如果T[j .. i]出现在S(Pi-1),也就是S(T[0 .. i-1]),中的时候,我们就不用改变树的结构了(当然需要还调整一些参数)。

      我们再来看,对于任何 j < i-1,如果T[j .. i]出现在S(T[0 .. i-1])中,那么T[j+1 .. i]也必然出现在S(T[0 .. i-1])中。下面给出证明:

    • 首先我们知道T[0..i-1] 的所有后缀都在后缀树中。
    • 其次,T[0..i-1] 的任意子串都可以表示为它的某一个后缀的前缀。
    • 所以 T[0..i-1] 的所有子串都在后缀树中。
    • T[j+1 .. i] 是 T[j..i] 的子串, T[j..i] 又是 T[0..i-1] 的子串(因为T[j .. i]出现在S(T[0 .. i-1])中),所以 T[j+1 .. i] 也是 T[0..i-1] 的子串。
    • 所以后缀树中存在 T[j+1 .. i]

    这也就是说如果尾部链表中某一个节点所代表的后缀加上ti,也就是T[j .. i],出现在S(T[0 .. i-1])中,那么链表后面的所有节点代表的后缀加上ti也都出现在S(T[0 .. i-1])中。

      故而所有这些点,无论是显式还是隐式节点都可以不用管了。

      这又是一个大优化!

    综合上面两个优化,我们知道事实上我们只需要处理原先尾部链表的中间一段节点就可以了,对于这些节点而言,每处理一次必定增加一个新叶子(为什么呢,因为这些节点既不是叶子节点,又不满足显或是隐式节点不用增加叶子的条件)。而”一朝为叶,终身为叶“,我们最终的后缀树S(T[0 .. n])只有n个叶子(其中tn=)。(为什么呢,因为不可能存在子串S = T[j .. n]+c’,因为这要求子串中之后还有字符,这是办不到的),这也就是说整个建树过程中我们一共只需要在尾部链表上处理n次就可以了,这是一个好兆头!

    种种迹象表明我们快到O(|T|)时间了,原理就先说这么多了。

    2、后缀树实现

    上文中提到我们最终只是需要沿着去除头尾之后的“尾部链表”以及根节点更新增加节点就好了。但是我们怎么来做呢?带着这个问题,正式进入我们的实现环节!

      首先引入两个概念:

    • 当前活跃点active point:这是一个三元组包含了三个信息(活跃点,活跃边,活跃半径)。初始值为(root,’\0x’,0),代表活跃点为根节点,没有活跃边,活跃长度为0;
    • 计数器remainder: 记录我们在当前阶段需要插入的叶子节点数目。注意到我们每次插入都会增加新的叶子节点,具体原因见上一篇文章。初始值为1,每次进入新阶段增加1,每次从活跃点新增一个叶子节点减少1。

    我们每一阶段的目标都是把当前阶段的所有后缀插入到后缀树中。至于叶子节点,我们跟上文所说的一样,采用   [ , #]格式,每到一个新的阶段自动更新。

      好了,下面给出构建后缀树的三个定理:

    规则一(活跃点为根节点时候的插入):

    • 插入叶子之后,活跃节点依旧为根节点;
    • 活跃边更新为我们接下来要更新的后缀的首字母;
    • 活跃半径减1;

    规则二(后缀链表):

    • 每个阶段,当我们建立新的内部节点并且不是该阶段第一次建立内部节点的时候,我们需要用指针从当前内部节点指向本阶段最近一次建立的内部节点

    规则三(活跃点不为根节点时候的插入):

    • 如果当前活跃点不是根节点,那么我们每次从活跃点新增一个叶子之后,就要沿着后缀链表到达新的点,并更新活跃节点;如果不存在后缀链表了,我们就转移到根节点,将活跃节点更新为根节点。活跃半径以及活跃边不变。

     

    是不是感觉这里面的“后缀链表”跟我们之前谈到的尾部链表非常相似啊,而且这个活跃点的概念是不是跟之前的尾部链表也有千丝万缕的关系呢,哈哈。留这些疑问!待会儿再说。我们先来通过一个例子来具体体验一把怎么建立后缀树。例子来自上文中提到的那篇原文。

      我们为字符串abcabxabcd建立后缀树吧。

      一开始活跃点三元组为(root,’\0’,0),计数器remainder为1;

    第一阶段,插入字符a,#=1。

    我们从当前活跃节点(根节点)出发看看有没有那个边的第 0(活跃半径) 个字母是a,发现没有,于是按照规则一插入叶子节点。活跃边更新为接下来要插入的后缀首字母,但是由于已经没有需要插入的了,故而活跃边也不变便;由于活跃半径已经是0,故而不用减1了;计数器remainder减少1变成0。我们获得了这样一棵树

    clip_image001

      因为当前#=1,故而上图的这个后缀树就是下图(注意一下,区间[0,1]的含义是第一个字符,这点跟之前的表示方法不太一样)

    clip_image002

      此时三元组为(root,’\0’,0),remainder为0;

    第二阶段,插入字符b,#=2; 三元组不变仍为(root,’\0’,0),remainder增加1,等于1;

    我们从当前活跃节点(根节点)出发看看有没有哪个边的第 0(活跃半径) 个字母是b,发现没有,于是按照规则一插入叶子节点。情况同上,三元组为(root,’\0’,0),remainder为0;我们获得了这样一棵树:

    clip_image003clip_image004

      因为#=2,故而左图等同于右图。

    第三阶段,插入字符c;#=3;三元组不变仍为(root,’\0’,0),remainder增加1,等于1;

    跟第二阶段类似,三元组为(root,’\0’,0),remainder为0;我们获得了这样一棵树:

    clip_image005clip_image006

      因为#=3,故而左图等同于右图。

     

    第四阶段,插入字符a; #=4; 三元组为(root,’\0’,0),remainder增加1,等于1;

    这时,我们从当前活跃节点(根节点)出发看看有没有哪个边的第 0(活跃半径) 个字母是a。结果发现了!!!那么此时,我们更新三元组为(root, ‘a’, 1), remainder不变。更新完系数之后,我们就进入下一阶段了。

    为什么?还记得上一篇文章中,”当新后缀出现在原先后缀树中”是怎么办么?哈哈,就是更新系数后不管了。

    我们获得了这样一棵树:

    clip_image005[1]clip_image007

    看出来了吧,树的形状没有变,但是叶子节点的边自动更新了。这也就是上一篇文章中提到了自动更新叶节点。按上文的说法这里应该有尾部链表从第一个点(边为abca)指向第二个点(边为bca),第二个点指向第三个点(边为ca),第三个点指向根节点,但是呢,显然这个链表上除了根节点都是叶节点,没有保存的必要啊。所以这里没有看到“尾部链表”的痕迹。这也是一种优化,但是,后面你会见到它的。哈哈,所谓神龙见首不见尾!我们接着来看。

    第五阶段,插入字符b;#=5; 三元组为(root,’a’,1),remainder增加1,等于2;

    这时,我们从当前活跃点(根节点)出发看看边首字母为a(活跃边)的第1(活跃半径)个字母是b。结果又发现了!!

    注意一下,之前因为没有明确的活跃边,故而可以随便找边,但是确定了活跃边之后就只能沿着活跃边来找了。

    因为这一次我们需要插入的后缀除了b之外,还有上次剩余的,故而我们需要插入的后缀是ab ,b。活跃边不变,只是活跃半径需要增加1,等于2。于是三元组变成了(root,’a’,2),计数器remainder不变,仍然为2。

    我们获得了这样一棵树:

    clip_image008

     

    第六阶段,插入字符x; #=6; 三元组为(root,’a’,2), remainder增加1,等于3;我们需要插入的后缀有abx,bx,x

    这时,我们从当前活跃点(根节点)出发看看沿着活跃边(边首字母为a)的第2(活跃半径)个字母是不是x。结果没发现!

    于是我们按照规则一,从当前生长点(活跃点沿着活跃边走活跃半径个字符)增加一个叶子,插入x,也就是代表了abx。

    获得了这个树:

    clip_image010

    插入完abx之后我们需要插入bx了,但是我们需要先调整三元组。活跃边首字母就应该变成b了,活跃半径减少1,于是我们的三元组变成了(root,’b’,1),remainder减少1,等于2。根据规则一,我们再从当前活跃点(根节点)出发看看沿着活跃边(边首字母为b)的第1(活跃半径)个字母是不是x。结果不是!于是再按照规则一,从当前生长点(活跃点沿着活跃边走活跃半径个字符)增加一个叶子,插入x,也就代表了bx。

      我们获得了这个树:

    clip_image011

    但是还没完,因为这已经是我们在此阶段建立的第二个内部节点了,根据规则二,故而我们需要建立”后缀链表”。此时三元组变成(root,’x’,0), remainder减少1,等于1。

    clip_image012

    接下来就要插入x了。此时活跃半径已经是0了,于是活跃边一定是空的了,我们查看根节点所有边中首字母有没有是x的,结果没有,于是插入x。从当前生长点(此时因为活跃半径是0,活跃点就是生长点)增加叶子,插入x。得到下面这颗树。根据规则一,此时的三元组变成了(root, ‘\0’, 0),remainder减少1,等于0。此阶段顺利结束了。

    clip_image013

     

    第七阶段,插入字符a;#=7;三元组为(root, ‘\0’, 0),remainder增加1,等于1。需要增加的后缀只有一个就是a;

    还是一样,鉴于活跃半径为0,我们从看看根节点有那个边的首字母为a,结果发现了。于是我们调整三元组为(root,’a’,1)。结束

    第八阶段,插入字符b;#=8;三元组为(root, ‘a’, 1),remainder增加1,等于2。需要增加的后缀有两个ab,b;

    我们先从当前活跃节点(根节点)出发,沿着活跃边的第1(活跃半径)个字符是不是b,结果是!于是我们调整三元组为(root, ‘a’, 2)。

    注意了,我们已经来到了一个内部节点而不再跟以前一样停留在边上,于是我们再次调整三元组(类似于初始化)为(node1,’\0’,0)。这里,node1代表了上图中从根节点出发经过边ab,到达的那个点。

    第九阶段,插入字符c;#=9;三元组为(node1,’\0’,0),remainder增加1,等于3。需要增加的后缀有三个abc,bc,c;

    鉴于活跃半径为0,我们直接看看当前活跃点(也就是node1)的边有没有以c为首字母的。结果有,于是更新三元组(node1,’c’,1)。注意一下虽然此时应该最先插入后缀abc,但是由于活跃点已经变化了,我们以当前活跃点为基准,故而活跃边以’c’标志。

    第十阶段,插入字符s;;#=10;三元组为(node1,’c’,1),remainder增加1,等于4。需要增加的后缀有四个abcd,bcd,cd,d;

    我们从当前活跃点node1出发沿着活跃边c,第1个字符是否是d,发现不是!于是在当前生长点(活跃点沿着活跃边前进活跃半径个字符)增加一个叶子,得到下图的树。

    clip_image014

    由于当前活跃点不是根节点,所以按照规则三,我们沿着后缀链表前进,更新三元组为(node2,’c’,1),remainder减少1,等于3。node2为下图中的红色点。

    clip_image015

    从node2出发沿着活跃边c出发,第1个字符是不是d,发现不是,于是在当前生长点增加叶子。注意此时要按照规则二建立新的后缀链表了。

    clip_image016

     

    按照规则三,沿着后缀链表,由于已经没有下一个节点了,于是跳回到根节点,更新三元组(root,’c’,1)。remainder减少1,等于2.

    从根节点出发沿着活跃边c,第1个字符是不是d?发现不是,于是在当前生长点增加叶子,注意仍按按照规则二建立后缀链表

    clip_image018

    之后按照规则一更新三元组,活跃点不变,当前带插入的后缀是d,故而修改活跃边为d,活跃半径减少1变成0。remainder减少1,等于1。

    现在插入后缀d,鉴于活跃半径为0,看看根节点有没有边是以d为首字母的,发现没有!于是增加叶子。

    clip_image019

    至此,全都结束了!后缀树建立完毕

    看完上面的建树过程,有点晕吧,哈哈,其实我也是。现在来说说上述算法跟上一篇文章提到的方法之间的关联吧。

    上一篇文章中我们提到的方法是每次沿着优化后的尾部链表更新,增加叶节点。其实我们这么来看,整个尾部链表是由三部分组成的,第一部分是叶子节点;第二部分是“除根节点外会增加叶子的节点”;第三部分是会导致 新后缀出现在原先后缀树中 的节点,这部分节点对树结构没有影响;所谓优化后的尾部链表是指去除第一部分和第三部分。当然喽第二部分第三部分都可能是空的。这样一来其实优化后的尾部链表由两部分组成:“尾部链表”的一部分(在本算法中就是后缀链表)。但是理论上这么说就可以了,实际上怎么来实现呢?

    我们看一下,因为”一朝为叶,终身为叶”,而每次遍历后缀链表的时候都会增加一个叶子,而最终的后缀树也只有|T|个叶子,所以我们一共需要遍历后缀链表|T|次。显然了,后缀链表是很“少”的。故而我们再去保留尾部链表,然后去定位第一个非叶子节点就很划不来了。于是,尾部链表作为一个理解上面的工具,在实践中(上述算法)就不维护啦,我们直接采用后缀链表。

    于是乎,我们回过头来看看上述算法。

    remainder是计数器,表明到当前阶段还需插入几个后缀,每个阶段增加1,是代表了后缀–从当前将要被插入的字符开始到原始串尾的这个后缀。当也叶子被插入的时候,rremainder减少1。

    首先初始化的时候活跃点是根节点,活跃半径是0。于是我们开始准备插入一个字符,如果字符没在根节点的任何一条边(默认为链接各个儿子的边)中出现,那么表明什么意思?表明当前生长点(根节点,所谓生长点就是准备长叶子的点),就是我们“尾部列表中”第二部分的节点,而remainder为1,代表当前只需插入一个叶子,于是插入即可,remainder减少1;如果字符在根节点的某一条边中出现,那么这是什么意思?这表明当前生长点(根节点),是我们第三部分的点,于是我们调整一下当前生长点的位置,这是为什么呢?因为,假设当前要插入的字符是a,下一次要插入b,那么我们这一阶段没插入叶子,下一阶段多了一个“欠债“,就要还要插入ab。那么我们将生长点挪到树中字符a的后面,就意味着我们下一阶段只需要在生长点后面插入字符b就可以了,一步到位,方便快捷。鉴于本阶段没有插叶子,所以remainder不变。调整三元组也是为了”挪动生长点“。

    下一次,我们要插入字符b的时候,我们在当前生长点后面找一找有没有b(其实就是为了验证当前生长点是不是后缀链表中的第三部分的点),如果没有,意味着是第二部分的点(因为肯定不是叶节点,又不是第三部分的点),那么就插入叶节点吧,remainder减少1,调整活跃边为下一个需要插入后缀的首字母,也就是b,活跃半径减少1。这也是为了调整生长点(快速找到下一个插入叶子的点)。于是看看根节点哪个边首字母为b,如果没有就插入新节点,如果有就调整生长点(这一块跟前面类似,不再多说)。我们说说另一种情况,就是我们在生长点(root,’a’,1)之后还找到了b,这说明当前生长点是第三部分的点,那么怎么办呢,继续调整生长点为(root,’a’,2)。

    假设上一次之后,调整生长点为(root,’a’,2),这一次再插入字符c,remainder增加1,等于3。如果当前生长点后没有c,意味着当前生长点是第二部分的点,于是插入叶子c就好了,代表着”欠债“后缀abc。remaidner减少1,调整生长点为(root,’b’,1),为什么如此确定根节点有某条边是以b为首字母呢?原因是这样的,你看啊,我们活跃半径是2,必然是因为我们刚刚插入的那个后缀abc的前两个字符出现在后缀树中,既然ab出现在了后缀树中,那么依据前文中的原理,b也一定出现在后缀树中。大家发现没有,这个调整生长点的过程是不是太迅速啦。

    事实上来说我们就凭借上述的这个过程似乎已经建立后缀树了,但是我们仔细看看,如果定位生长点的时候的这个(root,’a’,2)中的活跃半径不是2,而是一个很大的数字,比如100,那么就算我们知道下一个生长点是(root,’b’,99),真的能定位到准确的生长点么??不一定吧,根节点沿着一条特定的边走99步,可不一定只能到一个点啊,哈哈!

    这就是问题所在,所以我们调整生长点为(root,’a’,2)的时候,如果从当前活跃点开始,沿着活跃边走了活跃半径个距离,我们停在活跃边上面一个隐式节点那就没事,要是停到了内部节点node1,那我们就要更新活跃点为这个内部节点啦!然后调整三元组为(node1,’\0’,0)了。这里假设我们将(root,’a’,2)更新为(node1,’\0’,0)。我们再来看一下,假设下一个字符是c,且node1后面有一个边是以c为首字母的,于是更新三元组为(node1,’c’,1);假设我们之后要插入字符x,而从node1开始没有那个边是以x为首字母的,这时候就要插入叶子x了,代表了后缀abcx,我们下一个就要插入后缀bx了,但是怎么定位到下一个生长点?跟前面一样更新生长点为(node1,’b’,0)?

    肯定不行啊,因为下一个生长点根本就不在node1的子树里面。为什么?因为node1的子树里面任何一个点代表的字符串都是以ab(也就是根节点到node1那个边),而我们插入的是bcx。那么下一个生长点是什么呢?我们猜测一下啊,应该是(node2,’c’,1)其中根节点到node2的路径上面的字符是b!这样就可以啦。首先我们来明确一下存不存在这样一个结果node2的生长点?是存在的,因为既然后缀树中有ab这个内部节点(注意我的用词,ab已经成为i类不节点了,而不是刚刚建立的),那么必然有b这个内部节点(因为假设node1后面的两个儿子分别为x,y,那么后缀树中存在abx,和aby那么也必然存在bx,by所以也必然存在node2);同时后缀树中有字符串abc,那么必然也有串bc,于是证明是有的!下一个问题是,我们怎么快速将生长点从(node1,’c’,1)定位到(node2,’c’,1),所以我们想要是有一条指针从node1指向node2就好了,所以我们应该之前建立这个后缀链表这样下次就方便了。

    什么时候建立呢?我们来看啊,当初我们建立ab这个内部节点的时候,内部节点或者是已经存在了或者下一步就存在(注意跟上面的对比啊,这次是说我们当初建立ab内部节点的时候,所以这个内部节点是刚建立的,故而内部节点b暂时还不一定存在)为什么说下一步就存在呢?(因为: 如果 aS 停在一个内部节点上面,也就是 aS 后有分支,那么当前的 T[0 .. i-1] 肯定有子串 aS+c 以及aS+d ( c 和 d 是不同的两个字符) 这两个不同的子串,于是肯定也有 S+c 以及 S+d 两个子串了。至于“下次扩展时产生”的这种情况,则发生在已经有 aS+c 、 S+c ,刚加入 aS+d (于是产生了新的内部节点),正要加入 S+d 的时候。)下面我们来看啊,既然”下一步”内部节点b一定存在了,那就在”下一步”的时候建立指针从内部节点ab指向内部节点b。

    当我们走到后缀链表的尾部时候,意味着我们已经处理完毕remainder的前两个(就是从根节点到node1的边长,这两个后缀意味着abcx,bcx)”欠债”。于是我们回到根节点,当然了,活跃边和活跃半径不变。那么为什么此时从根节点出发沿着活跃边走活跃半径个字符就能唯一锁定生长点呢?

    答案是这样的,因为啊,我们之前将活跃点更新为node1之后可能还是会更新活跃点,我们将最后更新的活跃点命名为nodeN,此时的三元组为(nodeN,active_edge,active_length),我们知道这个三元组确定的生长点位于nodeN的某条边上的一个隐式节点。我们知道我们路过nodeN这个活跃点的时候,nodeN那边已经存在后缀链接了,所以当我们沿着后缀链接插入叶子,在最终回到根节点时候三元组变为nodeN(root,active_edge,active_length)。一步定位!而且在沿着后缀链表定位生长点的时候也是一步定位!

    下面说明一下为什么上述算法是线性的。首先啊,我们来看上面一共涉及到了几个操作:插入叶节点(每次插入消耗常数时间,总叶节点|T|个,故而总时间为O(|T|),建立后缀链表(每次建立一个指针只需要沿着前面建好的后缀链表走一下,然后一步定位,所以每次建立一个指针只需要常数时间;而每次我们沿着后缀链表走都会插入新叶子,故而后缀链表一共也只有|T|这么长,故而一共需要插入O(|T|)次),更新三元组(因为涉及到活跃点的移动,故而我们这么看,没有更新活跃点的时候是常数时间,而更新活跃点的情况有点复杂,我们这么理解:每次更新活跃点都会导致活跃半径相应减小,而活跃半径始在整个建树的过程中最多增加|T|,故而整个更新活跃点所需时间为O(|T|)),其他诸如remainder的调整等等,每次花费常数时间,总和为O(|T|)。综上所述,线性算法如下:

    #include <iostream>
    #include <stdio.h>
    #include <string>
    
    const int oo = 1<<25;
    const int ALPHABET_SIZE = 256;
    const int MAXN = 5000;
    
    using namespace std;
    
    int root, last_added, pos, needSL, remainder,
        active_node, active_e, active_len;
    
    struct node {
    /*
       There is no need to create an "Edge" struct.
       Information about the edge is stored right in the node.
       [start; end) interval specifies the edge,
       by which the node is connected to its parent node.
    */
    
        int start, end, slink;
        int next[ALPHABET_SIZE];    
    
        int edge_length() {
            return min(end, pos + 1) - start;
        }
    };
    
    node tree[2*MAXN];
    char text[MAXN];
    
    int new_node(int start, int end = oo) {
        node nd;
        nd.start = start;
        nd.end = end;
        nd.slink = 0;
        for (int i = 0; i < ALPHABET_SIZE; i++)
            nd.next[i] = 0;
        tree[++last_added] = nd;
        return last_added;
    }
    
    char active_edge() {
        return text[active_e];
    }
    
    void add_SL(int node) {
        if (needSL > 0) tree[needSL].slink = node;
        needSL = node;
    }
    
    bool walk_down(int node) {
        if (active_len >= tree[node].edge_length()) {
            active_e += tree[node].edge_length();
            active_len -= tree[node].edge_length();
            active_node = node;
            return true;
        }
        return false;
    }
    
    void st_init() {
        needSL = 0, last_added = 0, pos = -1, 
        remainder = 0, active_node = 0, active_e = 0, active_len = 0;
        root = active_node = new_node(-1, -1);
    }
    
    void st_extend(char c) {
        text[++pos] = c;
        needSL = 0;
        remainder++;
        while(remainder > 0) {
            if (active_len == 0) active_e = pos;
            if (tree[active_node].next[active_edge()] == 0) {
                int leaf = new_node(pos);
                tree[active_node].next[active_edge()] = leaf;
                add_SL(active_node); //rule 2
            } else {
                int nxt = tree[active_node].next[active_edge()];
                if (walk_down(nxt)) continue; //observation 2
                if (text[tree[nxt].start + active_len] == c) { //observation 1
                    active_len++;
                    add_SL(active_node); //observation 3
                    break;
                }
                int split = new_node(tree[nxt].start, tree[nxt].start + active_len);
                tree[active_node].next[active_edge()] = split;
                int leaf = new_node(pos);
                tree[split].next[c] = leaf;
                tree[nxt].start += active_len;
                tree[split].next[text[tree[nxt].start]] = nxt;
                add_SL(split); //rule 2
            }
            remainder--;
            if (active_node == root && active_len > 0) { //rule 1
                active_len--;
                active_e = pos - remainder + 1;
            } else
                active_node = tree[active_node].slink > 0 ? tree[active_node].slink : root; //rule 3
        }
    }
    
    int main() {
        //
        return 0;
    }

    最长回文问题的解决

    有了上面的概念,本文引言中提出的查找最长回文问题就相对简单了。咱们来回顾下引言中提出的回文问题的具体描述:找出给定字符串里的最长回文。例如输入XMADAMYX,则输出MADAM。

    思维的突破点在于考察回文的半径,而不是回文本身。所谓半径,就是回文对折后的字串。比如回文MADAM 的半径为MAD,半径长度为3,半径的中心是字母D。显然,最长回文必有最长半径,且两条半径相等。还是以MADAM为例,以D为中心往左,我们得到半径 DAM;以D为中心向右,我们得到半径DAM。二者肯定相等。因为MADAM已经是单词XMADAMYX里的最长回文,我们可以肯定从D往左数的字串 DAMX与从D往右数的子串DAMYX共享最长前缀DAM。而这,正是解决回文问题的关键。现在我们有后缀树,怎么把从D向左数的字串DAMX变成后缀 呢?

    到这个地步,答案应该明显:把单词XMADAMYX翻转(XMADAMYX=>XYMADAMX,DAMX就变成后缀了)就行了。于是我们把寻找回文的问题转换成了寻找两坨后缀的LCA的问题。当然,我们还需要知道 到底查询那些后缀间的LCA。很简单,给定字符串S,如果最长回文的中心在i,那从位置i向右数的后缀刚好是S(i),而向左数的字符串刚好是翻转S后得到的字符串S‘的后缀S'(n-i+1)。这里的n是字符串S的长度。

            可能上面的阐述还不够直观,我再细细说明下:

            1、首先,还记得本第二部分开头关于后缀树的定义么: “先说说后缀的定义,顾名思义,甚至通俗点来说,就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn,和整数i,1 <= i <= n,子串SiSi+1...Sn便都是字符串S的后缀。”。以字符串S=XMADAMYX为例,它的长度为8,所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀,我们一般还把空字串也算成后缀。这样,我们一共有如下后缀。对于后缀S[i..n],我们说这项后缀起始于i。

    S[1..8], XMADAMYX,也就是字符串本身,起始位置为1
    S[2..8],   MADAMYX,起始位置为2
    S[3..8],      ADAMYX,起始位置为3
    S[4..8],        DAMYX,起始位置为4
    S[5..8],           AMYX,起始位置为5
    S[6..8],             MYX,起始位置为6
    S[7..8],                YX,起始位置为7
    S[8..8],                  X,起始位置为8
                                     空字串,记为$。

        ​​​​​​​    ​​​​​​​2、对单词XMADAMYX而言,回文中心为D,那么D向右的后缀DAMYX假设是S(i)(当N=8,i从1开始计数,i=4时,便是S(4..8));而对于翻转后的单词XYMADAMX而言,回文中心D向右对应的后缀为DAMX,也就是S'(N-i+1)((N=8,i=4,便是S‘(5..8)) 。此刻已经可以得出,它们共享最长前缀,即LCA(DAMYX,DAMX)=DAM。有了这套直观解释,算法自然呼之欲出:

    1. 预处理后缀树,使得查询LCA的复杂度为O(1)。这步的开销是O(N),N是单词S的长度 ;
    2. 对单词的每一位置i(也就是从0到N-1),获取LCA(S(i), S‘(N-i+1)) 以及LCA(S(i+1), S’(n-i+1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i,所以复杂度是O(N) ;
    3. 找到最大的LCA,我们也就得到了回文的中心i以及回文的半径长度,自然也就得到了最长回文。总的复杂度O(n)。 

        ​​​​​​​    ​​​​​​​用上图做例子,i为4时,LCA(4$, 5#)为DAM,正好是最长半径。当然,这只是直观的叙述。
        
        ​​​​​​​上面大致描述了后缀树的基本思路。要想写出实用代码,至少还得知道下面的知识:

    • 创建后缀树的O(n)算法。此算法有很多种,无论Peter Weiner的73年年度最佳算法,还是Edward McCreight1976的改进算法,还是1995年E. Ukkonen大幅简化的算法(本文第4部分将重点阐述这种方法),还是Juha Kärkkäinen 和 Peter Sanders2003年进一步简化的线性算法,都是O(n)的时间复杂度。至于实际中具体选择哪一种算法,可依实际情况而定。 
    • 实现后缀树用的数据结构。比如常用的子结点加兄弟节点列表,Directed 优化后缀树空间的办法。比如不存储子串,而存储读取子串必需的位置。以及Directed Acyclic Word Graph,常缩写为黑哥哥们挂在嘴边的DAWG。 

    3、后缀树的应用

    后缀树的用途,总结起来大概有如下几种 

    1. 查找字符串o是否在字符串S中。 
        方案:用S构造后缀树,按在trie中搜索字串的方法搜索o即可。 
        原理:若o在S中,则o必然是S的某个后缀的前缀。 
      例如S: leconte,查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提,采用trie搜索的方法就不难理解了。。 
    2. 指定字符串T在字符串S中的重复次数。 
        方案:用S+’$'构造后缀树,搜索T节点下的叶节点数目即为重复次数 
        原理:如果T在S中重复了两次,则S应有两个后缀以T为前缀,重复次数就自然统计出来了。。 
    3. 字符串S中的最长重复子串 
        方案:原理同2,具体做法就是找到最深的非叶节点。 
        这个深是指从root所经历过的字符个数,最深非叶节点所经历的字符串起来就是最长重复子串。 
      为什么要非叶节点呢?因为既然是要重复,当然叶节点个数要>=2。 
    4. 两个字符串S1,S2的最长公共部分 
        方案:将S1#S2$作为字符串压入后缀树,找到最深的非叶节点,且该节点的叶节点既有#也有$(无#)。

     

    本文转载自:

    地址:http://www.cnblogs.com/xubenben/p/3486007.html

    地址:https://blog.csdn.net/v_JULY_v/article/details/6897097

    展开全文
  • 主要介绍了C语言数据结构之中缀树转后缀树的实例的相关资料,需要的朋友可以参考下
  • 后缀树的c++实现

    2018-05-27 23:04:07
    本压缩文件是关于后缀树的,包括后缀树的构建(采用Ukkonen算法),利用构建的后缀树进行字符串的查找。
  • 后缀树有一个缺点就是很费空间。那么能不能用后缀数组来实现这样的功能呢,当然是可以的,那就是增强后缀数组(enhanced suffix arrays)。增强后缀数组能模拟后缀树的大部分的结构,所谓增强后缀数组就是在后缀数组的...
  • 后缀树构造与应用

    2017-08-20 22:00:42
    关于后缀树Ukkonen算法的解释,以https://www.oschina.net/translate/ukkonens-suffix-tree-algorithm-in-plain-english网站讲解为基础
  • 一个C++源代码文件,包含详细的注释。 实现了广义后缀树的构造,及树状结构输出。 VS2012中运行成功。
  • 谢谢
  • 这是 Esko Ukkonen 在线后缀树构建算法的 C 语言基本实现。 它旨在作为一种教学工具,因为我发现有很多关于算法如何真正线性的数学解释,还有很多写得不好且难以遵循的实现。 从任何一个来源都很难确切地确定如何...
  • java后缀树代码

    2019-05-24 02:02:02
    NULL 博文链接:https://ganting.iteye.com/blog/371728
  • 经典的后缀树入门,后缀树组稍后共享,从零开始学数据结构。
  • 名称-tagger.hs 使用后缀树快速查找文本中的名称。 从要标记的名称字典开始处理。 重复:输入输入文本并获得匹配项作为响应! 字典格式: $id1\t$name1 $id2\t$name2
  • 前缀树和后缀树

    千次阅读 2019-02-28 15:43:24
    Trie的应用: 除了本文引言处所述的问题能应用Trie解决之外,Trie还能解决下述问题(节选自此文:海量数据处理面试题集锦与Bit-map详解): 3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16...

    Trie树的应用:

       除了本文引言处所述的问题能应用Trie树解决之外,Trie树还能解决下述问题(节选自此文:海量数据处理面试题集锦与Bit-map详解):
    3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
    9、1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?
    10、 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
    13、寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。
    (1) 请描述你解决这个问题的思路;
    (2) 请给出主要的处理流程,算法,以及算法的复杂度。
        有了Trie,后缀树就容易理解了。本文接下来的第二部分,介绍后缀树

    前缀树:

    前缀树又名字典树,单词查找树,Trie树,是一种多路树形结构,是哈希树的变种,和hash效率有一拼,是一种用于快速检索的多叉树结构。

    典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    Trie树也有它的缺点,Trie树的内存消耗非常大。

    性质:不同字符串的相同前缀只保存一份。

    操作:查找,插入,删除。

    举个栗子:给出一组单词,inn, int, at, age, adv,ant, 我们可以得到下面的Trie:

    从上面可以发现一些Trie树的特性:

    1)根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

    2)从根节点到某一节点的路径上的字符连接起来,就是该节点对应的字符串。

    3)每个节点的所有子节点包含的字符都不相同。

    4)每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。

    单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

    前缀树的应用

    前缀树还是很好理解,它的应用也是非常广的。

    (1)字符串的快速检索

    字典树的查询时间复杂度是O(logL),L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。

    hash表:

    通过hash函数把所有的单词分别hash成key值,查询的时候直接通过hash函数即可,都知道hash表的效率是非常高的为O(1),当然这是对于如果我们hash函数选取的好,计算量少,且冲突少,那单词查询速度肯定是非常快的。那如果hash函数的计算量相对大呢,且冲突律高呢?这些都是要考虑的因素。

    还有就是hash表不支持动态查询,什么叫动态查询,当我们要查询单词apple时,hash表必须等待用户把单词apple输入完毕才能hash查询。当你输入到appl时肯定不可能hash吧。

    字典树(tries树):

    对于单词查询这种,还是用字典树比较好,但也是有前提的,空间大小允许,字典树的空间相比较hash还是比较浪费的,毕竟hash可以用bit数组。

     

    (2)字符串排序

    从上图我们很容易看出单词是排序的,先遍历字母序在前面。

    减少了没必要的公共子串。

     

    (3)最长公共前缀

    inn和int的最长公共前缀是in,遍历字典树到字母n时,此时这些单词的公共前缀是in。

    (4)自动匹配前缀显示后缀

    我们使用辞典或者是搜索引擎的时候,输入appl,后面会自动显示一堆前缀是appl的东东吧。

    那么有可能是通过字典树实现的,前面也说了字典树可以找到公共前缀,我们只需要把剩余的后缀遍历显示出来即可。

    后缀树

    后缀树,就是把一串字符的所有后缀保存并且压缩的字典树。相对于字典树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串等等。

    性质:一个字符串构造了一棵树,树中保存了该字符串所有的后缀。

    操作:就是建立和应用。

     

    (1)建立后缀树

    比如单词banana,它的所有后缀显示到下面的。0代表从第一个字符为起点,终点不用说都是字符串的末尾。

    以上面的后缀,我们建立一颗后缀树。如下图,为了方便看到后缀,我没有合并相同的前缀。

    前面简介的时候我们说了,后缀树是把一个字符串所有后缀压缩并保存的字典树。所以我们把字符串的所有后缀还是按照字典树的规则建立,就成了下图的样子。这就是后缀树的压缩,可见更加节省空间。

    最长回文问题的解决:

    思维的突破点在于考察回文的半径,而不是回文本身。所谓半径,就是回文对折后的字串。比如回文MADAM 的半径为MAD,半径长度为3,半径的中心是字母D。显然,最长回文必有最长半径,且两条半径相等。还是以MADAM为例,以D为中心往左,我们得到半径 DAM;以D为中心向右,我们得到半径DAM。二者肯定相等。因为MADAM已经是单词XMADAMYX里的最长回文,我们可以肯定从D往左数的字串 DAMX与从D往右数的子串DAMYX共享最长前缀DAM。而这,正是解决回文问题的关键。现在我们有后缀树,怎么把从D向左数的字串DAMX变成后缀 呢?

        到这个地步,答案应该明显:把单词XMADAMYX翻转(XMADAMYX=>XYMADAMX,DAMX就变成后缀了)就行了。于是我们把寻找回文的问题转换成了寻找两坨后缀的LCA的问题。当然,我们还需要知道 到底查询那些后缀间的LCA。很简单,给定字符串S,如果最长回文的中心在i,那从位置i向右数的后缀刚好是S(i),而向左数的字符串刚好是翻转S后得到的字符串S‘的后缀S'(n-i+1)。这里的n是字符串S的长度。

        可能上面的阐述还不够直观,我再细细说明下:

        1、首先,还记得本第二部分开头关于后缀树的定义么: “先说说后缀的定义,顾名思义,甚至通俗点来说,就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn,和整数i,1 <= i <= n,子串SiSi+1...Sn便都是字符串S的后缀。”

        以字符串S=XMADAMYX为例,它的长度为8,所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀,我们一般还把空字串也算成后缀。这样,我们一共有如下后缀。对于后缀S[i..n],我们说这项后缀起始于i。

    S[1..8], XMADAMYX, 也就是字符串本身,起始位置为1
      S[2..8], MADAMYX,起始位置为2
         S[3..8], ADAMYX,起始位置为3
           S[4..8], DAMYX,起始位置为4
              S[5..8], AMYX,起始位置为5
                S[6..8], MYX,起始位置为6
                   S[7..8], YX,起始位置为7
                     S[8..8], X,起始位置为8
                                      空字串,记为$。

        2、对单词XMADAMYX而言,回文中心为D,那么D向右的后缀DAMYX假设是S(i)(当N=8,i从1开始计数,i=4时,便是S(4..8));而对于翻转后的单词XYMADAMX而言,回文中心D向右对应的后缀为DAMX,也就是S'(N-i+1)((N=8,i=4,便是S‘(5..8)) 。此刻已经可以得出,它们共享最长前缀,即LCA(DAMYX,DAMX)=DAM。有了这套直观解释,算法自然呼之欲出:

    预处理后缀树,使得查询LCA的复杂度为O(1)。这步的开销是O(N),N是单词S的长度 ;
    对单词的每一位置i(也就是从0到N-1),获取LCA(S(i), S‘(N-i+1)) 以及LCA(S(i+1), S’(n-i+1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i,所以复杂度是O(N) ;
    找到最大的LCA,我们也就得到了回文的中心i以及回文的半径长度,自然也就得到了最长回文。总的复杂度O(n)。 
     

    参考博客:

    https://blog.csdn.net/v_july_v/article/details/6897097

    https://blog.csdn.net/u013949069/article/details/78056102

    展开全文
  • 后缀树 & c++代码实现

    千次阅读 2018-11-10 23:49:24
    后缀树----构建 1.后缀树简介 后缀树是一种数据结构,一个具有m个字符的字符串S的后缀树T,就是一个包含一个根节点的有向树,该树恰好带有m+1个叶子,这些叶子被赋予从0到m的标号。每一个内部节点,除了根节点以外,...

    后缀树----构建

    1.后缀树简介

    后缀树是一种数据结构,一个具有m个字符的字符串S的后缀树T,就是一个包含一个根节点的有向树,该树恰好带有m+1个叶子,这些叶子被赋予从0到m的标号。每一个内部节点,除了根节点以外,都至少有两个子节点,而且每条边都用S的一个子串来标识。出自同一节点的任意两条边的标识不会以相同的字符开始。后缀树的关键特征是:对于任何叶子i,从根节点到该叶子所经历的边的所有标识串连起来后恰好拼出S 的从i位置开始的后缀,即S[I,…,m]。(这里有一个规定,即字符串中不能有空格,且最后一个字符不能与前面任何一个字符相同)

    为了方便理解概念,给出一个例子,下图是字符串"banana#"的后缀树。

    在这里插入图片描述

    2.算法设计

    源代码参见我的Github

    本文章利用的是Ukkonen算法构建后缀树,在 1995 年,Esko Ukkonen 发表了论文《On-line construction of suffix trees》,描述了在线性时间内构建后缀树的方法。 本文章参考数据结构系列——后缀树(附Java实现代码),理解之后做了适当的改进并用c++语言实现,代码在dev-cpp 5.11已测试。

    首先解释一下将要用到的几个概念:活动点(包括活动节点,活动边,活动长度)剩余后缀数。活动点中的活动节点:是用于查找一个后缀是否已经存在这棵树里,即查找的时候从活动节点的子节点开始查找,同时当需要插入边的时候也是插入到该节点下;而活动边则是每次需要进行分割的边,即成为活动边就意味着需要被分割;而活动长度则是指明从活动边的哪个位置开始分割。剩余后缀数是我们需要插入的后缀的数量,说明程序员点就是缓存的数量,因为每次如果要插入的后缀存在,则缓存起来。另外还用到了后缀字符数组,表明将要处理的后缀字符。

    对于指定的字符串,从前往后一次提取一个字符,将其加入后缀字符数组,然后剩余后缀数加一,在当前后缀树中(当然,刚开始树是空的)寻找是否存在当前字符的后缀,如果有,则继续进行循环读取下一个字符,如果没有,则进入后缀字符处理函数进行后缀处理,在后缀处理函数中,首先需要定位活动节点,然后在依据活动节点来进行不同的操作。

    那么,先来了解一下几个规则:

    规则一(活动节点为根节点时候的插入):

    o插入叶子之后,活动节点依旧为根节点;

    o活动边更新为我们接下来要更新的后缀的首字母;

    o活动长度减1;

    规则二(后缀链表):

    o每个阶段,当我们建立新的内部节点并且不是该阶段第一次建立内部节点的时候, 我们需要用指针从当前内部节点指向本阶段最近一次建立的内部节点。

    规则三(活动节点不为根节点时候的插入):

    o如果当前活动节点不是根节点,那么我们每次从活动节点新建一个叶子之后,就要沿着后缀链表到达新的节点,并更新活动节点,如果不存在后缀链表,我们就转移到根节点,将活活动节点更新为根节点但活动长度以及活动边不变。

    额外规则(活动点的晋升)

    o如果活动边上的所有字符全部都被匹配完了(即活动边上的字符数==活动长度),则将活动边连接的下一个节点晋升为活动节点,同时重置活动长度为0。

    也就是说更新活动点后,如果活动节点是根节点则按照规则一进行处理,如果活动节点不是根节点,则按照规则三进行处理,在处理过程中,还要时刻注意规则二和额外规则。当新建节点时,遵循以下规则,如果新建时,活动边存在,则分裂活动边,分割的位置由活动长度指定;如果活动边不存在,则就在活动节点下新建节点和边。

    3.模块描述

    (1)数据类型

    首先定义结构变量及类,包括Node结构体,Edge结构体,ActivePoint结构体,以及SuffixTree类。

    Node结构体----后缀树中的节点

    struct Node
    {
    	int flag;
    	int count;//链接的边的个数,用下边的边指针数组存储 
    	Edge *child[max];
    	Edge *parent;
    	Node *next;//后缀链接标识 
    	Node(){flag=-1;parent=NULL;count=0;next=NULL;}
    	Node(int f){flag=f;parent=NULL;count=0;next=NULL;}
    };
    

    Edge结构体----后缀树中的边

    struct Edge
    {
    	string str;
    	Node *above,*below;//head-->above   back--->below 
    	Edge(){str="";above=NULL;below=NULL;}
    	Edge(Node *above,Node *below,string str)
    	{
    		this->str=str;
    		this->above=above;
    	    this->below=below;
    		this->above->child[above->count++]=this;
    		this->below->parent=this;
    	}
    	Edge(Node *above,int i,Node *below,string str)
    	{
    		this->str=str;
    		this->above=above;
    		this->below=below;
    		this->above->child[i]=this;
    		this->below->parent=this;
    	}
    };
    

    ActivePoint结构体----活动点

    struct ActivePoint
    {
    	Node *node;//活动节点 
    	Edge *edge;//活动边 
    	int length;//活动长度 
    	ActivePoint(){node=NULL;edge=NULL;length=0;}
    	ActivePoint(Node*n,Edge*e,int len){node=n;edge=e;length=len;}
    };
    

    SuffixTree类----后缀树类

    class SuffixTree
    {
    	public:
    		SuffixTree()
    		{
    			root=new Node();
    			activepoint=new ActivePoint(root,NULL,0);
    			reminder=0;
    			helpstr="";
    			suffixarray="";
    			active=NULL;
    		}
    		~SuffixTree(){delall(root);} //析构函数 
    		void delall(Node *p);//实际释放空间函数,释放节点p的所有孩子 (从后往前)
    		
    		int getlength(Node *p);//从p节点向上到根节点经历过的边的字符个数 
    		string getstr(Node *node);//从根节点向下到p节点拼出字符串 
    		string getallstr(){return helpstr;}//返回该树的字符串 
    		
    		bool search(Node *p,string str,Node *&cur);//从p节点向下寻找与字符串str匹配的,找到返回true 
    		bool findstr(string str);//查找字符串是否存在 
    		string findlongeststr();//寻找最长重复字符串 
    		void finddeepestr(Node *a[],Node *p,int &cal);//寻找每个分支的最长重复字符串 
    		
    		int count(string str);//计算字符串str出现的次数 
    		int countleaf(Node *p);//计算p节点下的叶节点个数 
    		bool judgeleaf(Node *p);//判断p节点先是否全为叶节点 
    		
    		int find(char x);//查找指定的后缀是否存在 
    		void build(string str);//构建后缀树 
    		void deal(string str,int currentindex);//处理后缀函数 
    		
    		void showtree(){show(root,0,0);}//打印后缀树 
    		void show(Node *p,int repeat,int len);//打印后缀树实际函数 
    		
    		void test()//测试用函数,展示当前活动点,后缀字符,剩余后缀数等信息 
    		{
    			if(activepoint->edge!=NULL)
    			{
    				cout<<"\n apnode="<<getstr(activepoint->node)<<",apedge="<<activepoint->edge->str<<",aplen="<<activepoint->length;
    		    	cout<<",reminder="<<reminder<<",suffixarray="<<suffixarray<<"\n";
    			}
    			else
    			{
    				cout<<"\n apnode="<<getstr(activepoint->node)<<",apedge=NULL,aplen="<<activepoint->length;
    		    	cout<<",reminder="<<reminder<<",suffixarray="<<suffixarray<<"\n";
    			}
    		}
    	private:
    		Node *root;
    		ActivePoint *activepoint;
    		int reminder;
    		string suffixarray;	
    		Node *active;
    		string helpstr;	
    };
    

    (2)算法描述

    build(String word):在SuffixTree中定义一个build(String word)方法,是后缀树构建的入口函数。首先依次提取字符串的每个字符,并按照算法步骤逐个插入。find(char w)用于查找指定的后缀是否存在(这里所说的后缀其实就是单个字符,因为单个字符代表的就是以该字符开头的后缀)。如果当前后缀未找到,就进入后缀字符处理函数deal(),如果找到,就继续循环。build()源代码如下,

    /****************************************************************************
    **build(string str)方法: 
    **以str构造后缀树 
    ****************************************************************************/
    void SuffixTree::build(string str)
    {
    	helpstr=str;
    	int index=0;
    	Edge *&apedge=activepoint->edge;
    	Node *&apnode=activepoint->node; 
    	int &aplen=activepoint->length;
    	
    	while(index<str.length())
    	{
    		//cout<<"\n当前处理的: "<<index<<","<<str[index]<<"\n";
    		//test();cout<<"\n" ;
    		int currentindex=index++;
    		char w=str[currentindex];
    		
    		//查找是否存在保存有当前后缀字符的节点 
    		if(find(w)!=-1)//如果找到了 
    		{
    			suffixarray+=w;
    			reminder++;
    			continue;
    		}
    		else //如果未找到 
    		{
    			suffixarray+=w;
    			reminder++;
    	    }
    		active=NULL;
    		deal(str,currentindex);
    		
    	}
    }
    

    find():查找后缀是否存在是从活动边开始查找,如果活动边为NULL,则从活动节点的子节点挨个查找,查找是通过比较边上的指定位置(活动长度指定)与查找字符是否相等。这里有个地方需要注意:算法中提到,如果一个活动边已到达结尾(即活动长度==活动边的字符长度),则将活动边晋升为活动节点,并重置活动边和活动长度为NULL和0。

    /****************************************************************************
    **int find(char x)方法: 
    **查找当前后缀是否存在,不存在返回-1 
    ****************************************************************************/
    int SuffixTree::find(char x)
    {
    	Edge *&apedge=activepoint->edge;
    	Node *&apnode=activepoint->node;
    	int &aplen=activepoint->length;
    	if(apedge==NULL)
    	{//无活动边,则从活动节点的子节点开始查找
    		for(int i=0;i<apnode->count;i++)
    		{
    			//cout<<i;
    			Edge *tempedge=apnode->child[i];
    		    if(tempedge->str[0]==x)
    		    {	  
    		        aplen++;
    		        apedge=apnode->child[i];
    		        if(aplen==apedge->str.length())
    	            {//这里出现了一个修改活动点的规则:即如果活动边上的所有字符全部都被匹配完了
    			     //(级活动边上的字符数==活动长度),则将活动边晋升为活动点,同时重置活动长度为0。
    			     //所以下次查找时就得从该节点开始了,而不是根节点了。
    			
    			        apnode=apedge->below;
    	    	        aplen=0;
    	    	        apedge=NULL;
    	    	        //return 1;
    		        }
    		    	return i;
    			}
    		       
    		}
    		return -1;
    	}
    	else
    	{// 有活动边,则在活动边上查找
    	    if(apedge->str[aplen]==x)
    	    {
    	    	aplen++;
    	        if(aplen==apedge->str.length())
    	        {//这里出现了一个修改活动点的规则:即如果活动边上的所有字符全部都被匹配完了
    			 //(级活动边上的字符数==活动长度),则将活动边晋升为活动点,同时重置活动长度为0。
    			 //所以下次查找时就得从该节点开始了,而不是根节点了。
    			
    			    apnode=apedge->below;
    	    	    aplen=0;
    	    	    apedge=NULL;
    		    }
    		    return 1;
    	    }
    	    else
    	        return -1;
    		    
    	}
    	return -1;
    }
    

    deal():该方法是用来处理后缀字符的,也是后缀树构建中的主要部分,主要就是依据上文提到的几个规则来进行,deal()源代码如下,

    /****************************************************************************
    **deal(string str,int currentindex,int number)方法: 
    **处理后缀字符,str是输入的字符,currentindex是处理到的位置,number表示本次操作
    **使用了几次后缀链表 
    ****************************************************************************/
    void SuffixTree::deal(string str,int currentindex)
    {
        //cout<<"\n----------------------------------------------\n";
    	//cout<<"deal函数入口:\n";
       // test();show(root,0,0);
        
    
    	Edge *&apedge=activepoint->edge;
    	Node *&apnode=activepoint->node;
    	int &aplen=activepoint->length;
    	if(reminder==1)//如果剩余后缀数为1 //pay attention to//是否一定为根,当reminder为1的时候 
    	{
    		if(apnode==root)//如果活动节点是根节点 
    		{//新建节点 
    			Node *tempnode1=new Node(currentindex-suffixarray.length()+1);
    			Edge *tempedge1=new Edge(apnode,tempnode1,str.substr(currentindex));
    			suffixarray.erase(0,1);
    			reminder--;
    			apedge=NULL;
    			
    			//cout<<"deal函数出口:\n";
                //test();show(root,0,0);
                //cout<<"\n----------------------------------------------\n";
    			return;
    		}
    		else//如果活动节点不是根节点,apnode!=root 
    		{
    			
    		}
    	}
    	else//剩余后缀数大于1
    	{
    		if(apnode==root)
    		{
    				//规则一(活跃点为根节点时候的插入):
                    //o插入叶子之后,活跃节点依旧为根节点;
                    //o活跃边更新为我们接下来要更新的后缀的首字母; 
                    //o活跃半径减1;
                    if(apedge==NULL)//如果活动边不存在,即说明活动节点下需要新创建节点
    				{
    					Node *tempnode1=new Node(currentindex);
    					Edge *tempedge1=new Edge(apnode,tempnode1,str.substr(currentindex));
    					//活动边依旧设置为空 		
    				} 
    				else
    				{
    						    Edge *edge=apedge;//保存当前活动边,也便于后边释放旧有的活动边 
    						    apedge=NULL;
    						    aplen--;//因为一定能找到,因此寻找过程中会使得aplen++,此处修正
    							int m=find(edge->str[0]);//寻找标号,后边新建节点会用到 
    							
    							 
    							Node *tempnode1=new Node();
    					        Edge *tempedge1=new Edge(tempnode1,apedge->below,apedge->str.substr(aplen));
    					        Edge *tempedge2=new Edge(apnode,m,tempnode1,apedge->str.substr(0,aplen));
    					        
    							Node *tempnode2=new Node(currentindex-suffixarray.length()+1);
    							Edge *tempedge3=new Edge(tempnode1,tempnode2,str.substr(currentindex));
    							
    				 			apedge=apnode->child[m];
    							delete edge;//释放旧有的活动边 
    								 
    					
    				    
    			 	    
    				}
                    
    				
    				
    				//规则二(后缀链表):
                    //o每个阶段,当我们建立新的内部节点并且不是该阶段第一次建立内部节点的时候,
                    //我们需要用指针从当前内部节点指向本阶段最近一次建立的内部节点。 
      
                    //如果当前新建节点是内部节点,则更新后缀链表 
                    if(apedge!=NULL&&apedge->below->count>1)
    				{
    					if(active==NULL)
    				        active=apedge->below;
    				    else
    				    {
    					    active->next=apedge->below;
    					    active=apedge->below;
    				    }
    				}
    				else if(apedge==NULL)
    				{
    					if(active==NULL)
    				        active=apnode;
    				    else
    				    {
    					    active->next=apnode;
    					    active=apnode;
    				    }
    				}
    				
    				
    				
    				suffixarray.erase(0,1);
    				reminder--;
    				aplen--;
    				
    				
    				apedge=NULL;//apnode已经为空 
    				aplen=0;
    			    int flag;
    				for(int i=0;i<reminder;i++)
    				{
    					flag=find(suffixarray[i]);
    			    }
    			    
    			    
    			    if(flag==-1)
    			    {
    			    	//cout<<"deal函数出口:\n";
                        //test();show(root,0,0);
                        //cout<<"\n----------------------------------------------\n";
    			    	deal(str,currentindex);
    			    	return;
    				}
    				else
    				{
    					//cout<<"deal函数出口:\n";
                        //test();show(root,0,0);
                        //cout<<"\n----------------------------------------------\n";
    					return;
    				}
    						
    					
    				
    		}
    		else//apnode!=root
    		{
    			    //规则三(活跃点不为根节点时候的插入):
                    //o如果当前活跃点不是根节点,那么我们每次从活跃点新建一个叶子之后,
                    //就要沿着后缀链表到达新的节点,并更新活跃节点,如果不存在后缀链表,
                    //我们就转移到根节点,将活跃节点更新为根节点但活跃半径以及活跃边不变。
                    
                    char temp;
    				if(apedge==NULL)//如果活动边不存在,即说明活动节点下需要新创建节点
    				{
    					Node *tempnode1=new Node(currentindex-suffixarray.length()+1);
    					Edge *tempedge1=new Edge(apnode,tempnode1,str.substr(currentindex));
    					//这个时候活动节点怎么定义???? //依旧当做新建的内部节点处理 	
    				}
    				else 
    				{
    					
    					
    					    Edge *edge=apedge;
    					    temp=edge->str[0];
    					    apedge=NULL;
    					    aplen--;
    						int m=find(edge->str[0]);
    						
    						
    						Node *tempnode1=new Node();
    						//cout<<"what happened?\n";//这里曾经出现一个问题就是前面的"aplen--"与"int m=find(edge->str[0])"顺序错误而产生的问题 
    						//cout<<apedge->str<<" "<<aplen;//当顺序反后,活动点可能会错误的升级,而这不是我想要的 
    						//cout<<apedge->str.substr(aplen)<<"\n";
    						Edge *tempedge1=new Edge(tempnode1,apedge->below,apedge->str.substr(aplen));
    					    Edge *tempedge2=new Edge(apnode,m,tempnode1,apedge->str.substr(0,aplen));
    					        
    						Node *tempnode2=new Node(currentindex-suffixarray.length()+1);
    						Edge *tempedge3=new Edge(tempnode1,tempnode2,str.substr(currentindex));
    						
    						apedge=apnode->child[m];	
    						delete edge;	
    				} 
    				reminder--;
    				suffixarray.erase(0,1);
    				
    				 //如果当前新建节点是内部节点,则更新后缀链表 
                    if(apedge!=NULL&&apedge->below->count>1)
    				{
    					if(active==NULL)//注意加判定以判断是否为内部节点!!! 
    				        active=apedge->below;
    				    else
    				    {
    					    active->next=apedge->below;
    					    active=apedge->below;
    				    }
    				}
    				else
    				{
    					if(active==NULL)//注意加判定以判断是否为内部节点!!! 
    				        active=apnode;
    				    else
    				    {
    					    active->next=apnode;
    					    active=apnode;
    				    }
    				
    				}
    				
    
    				//开始沿着后缀链表寻找,并且重置活动点 
    				if(apnode->next!=NULL)//如果有连接,就进入 
    				{
    					
    						apnode=apnode->next;
    					    apedge=NULL;
    					    int tempaplen=aplen;
    					    aplen=0;
    					    
    					   
    				        int flag;
    			            for(int i=reminder-tempaplen-1;i<reminder;i++)
    				        {
    					     flag=find(suffixarray[i]);
    			            }
    			            
    			            
    			            
    			            if(flag==-1)
    			            {
    			            	//cout<<"deal函数出口:\n";
                                //test();show(root,0,0);
                                //cout<<"\n----------------------------------------------\n";
    			    	        deal(str,currentindex);
    			    	        return;
    			           	}
    			        	else
    			        	{
    			        		//cout<<"deal函数出口:\n";
                                //test();show(root,0,0);
                                //cout<<"\n----------------------------------------------\n";
    					        return;
    				        }
    					 
    					
    				}
    				else//如果当前节点无连接,就置活动节点为根节点 
    				{
    					apnode=root;
    					apedge=NULL;
    					aplen=0;
    				    int flag;
    	    		    for(int i=0;i<reminder;i++)
    				    {
    					    flag=find(suffixarray[i]);
    			        }
    			        if(flag==-1)
    			        {
    			        	//cout<<"deal函数出口:\n";
                            //test();show(root,0,0);
                            //cout<<"\n----------------------------------------------\n";			        	
    			    	    deal(str,currentindex);
    			    	    return;
    			        }
    			        else
    			        {
    			        	//cout<<"deal函数出口:\n";
                           //test();show(root,0,0);
                            //cout<<"\n----------------------------------------------\n";			        	
    					    return;
    				    }
    					
    					
    				}
    		}//apnode!=root终结 
    		
    	}//reminder>1终结 
    	    
    } 
    
    展开全文
  • 后缀树&后缀数组&LCP

    2019-12-31 17:51:24
    后缀树: 字符串匹配算法一般都分为两个步骤,一预处理,二匹配。 KMP和AC自动机都是对模式串进行预处理,后缀树和后缀数组则是对文本串进行预处理。 后缀树的性质: 存储所有 n(n-1)/2 个后缀需要 O(n) 的空间,n ...

    后缀树:

    字符串匹配算法一般都分为两个步骤,一预处理,二匹配。

    KMP和AC自动机都是对模式串进行预处理,后缀树和后缀数组则是对文本串进行预处理。

    后缀树的性质

    • 存储所有 n(n-1)/2 个后缀需要 O(n) 的空间,n 为的文本(Text)的长度;
    • 构建后缀树需要 O(dn) 的时间,d 为字符集的长度(alphabet);
    • 对模式(Pattern)的查询需要 O(dm) 时间,m 为 Pattern 的长度;

    介绍后缀树之前,我们首先要知道压缩字典树的概念。

    我们在对关键字建立字典树的时候,有时某些节点只会有一个子树,没有别的支路。那么这个节点和他的子树就可以压缩成一个节点。

    比如,下面是集合 {bear, bell, bid, bull, buy, sell, stock, stop} 所构建的 Trie 树。

    他对应的压缩字典树就是这样的。

     

    而后缀树就是一棵以所有的后缀为关键字建立的压缩字典树

    比如,对于文本 "banana\0",其中 "\0" 作为文本结束符号。下面是该文本所对应的所有后缀。

    banana\0
    anana\0
    nana\0
    ana\0
    na\0
    a\0
    \0

    将每个后缀作为一个关键词,构建一棵 Trie。

    然后,将独立的节点合并,形成 Compressed Trie。

    则上面这棵树就是文本 "banana\0" 所对应的后缀树。

    像上面建立的其实是一棵显式后缀树,因为如果我们不在后缀后面加上\0.某些后缀比如a,na在其他后缀的前缀中出现过,他们会被表示在一条路径上,这样的后缀树被称为隐式后缀树

    在后缀后加入一个后缀中没有出现过的字符,如\0或是$可以保证后缀的唯一性,此时建立的就是一种显式后缀树

     

    后缀树 与 字典树 的不同在于,边(Edge)不再只代表单个字符,而是通过一对整数 [from, to] 来表示。其中 from 和 to 所指向的是 Text 中的位置,这样每个边可以表示任意的长度,而且仅需两个指针,耗费 O(1) 的空间。

     

     

    后缀数组:

    后缀树的建立相当的麻烦,后缀数组的提出就是为了代替后缀树,并且后缀数组节省了空间。因此题目中我们大多实现后缀数组。

     

    其与后缀树的的关系有:

     

    • 后缀数组可以通过对后缀树做深度优先遍历(DFT: Depth First Traversal)来进行构建,对所有的边(Edge)做字典序(Lexicographical Order)遍历。
    • 通过使用后缀集合和最长公共前缀数组(LCP Array: Longest Common Prefix Array)来构建后缀树,可在 O(n) 时间内完成,例如使用 Ukkonen 算法。构造后缀数组同样也可以在 O(n) 时间内完成。
    • 每个通过后缀树解决的问题,都可以通过组合使用后缀数组和额外的信息(例如:LCP Array)来解决。

     

    后缀数组就是将文本串的所有后缀按照字典序进行排序,将后缀的起始字符的下标存入SA数组中。

    比如字符串“ababa”, 他的后缀有ababa, baba, aba, ba, a

    按照字典序排序为,a, aba, ababa, ba, baba他们的开始字符的下标分别为,5, 3, 1, 4, 2。因此SA[1~5]分别为5,3,1,4,2

     同时我们可以用rank来记后缀在所有后缀里的排名

    构建SA[i]数组中相邻元素的最长公共前缀(LCP,Longest Common Prefix),Height[i]表示SA[i]和SA[i-1]的LCP(i, j);H[i]=Height[Rank[i]表示Suffix[i]和字典排序在它前一名的后缀子串的LCP大小;
    对于正整数i和j而言,最长公共前缀的定义如下: LCP(i, j) =lcp(Suffix(SA[i]), Suffix(SA[j])) = min(Height[k] | i + 1 <= k <= j)
    也就是计算LCP(i, j)等同于查找Height数组中下标在i+1到j之间的元素最小值

     

    暴力的构建后缀数组的方法复杂度是O(n^2logn),倍增算法(Doubling Algorithm)快速构造后缀数组,其利用了后缀子串之间的联系可将时间复杂度降至O(MlogN),M为模式串的长度,N为目标串的长度;另外基数排序算法的时间复杂度为O(N);Difference Cover mod 3(DC3)算法(Linear Work Suffix Array Construction)可在O(3N)时间内构建后缀数组;Ukkonen算法(On-line Construction of Suffix-Trees)可在O(N)的时间内构建一棵后缀树,然后再O(N)的时间内将后缀树转换为后缀数组,理论上最快的后缀数组构造法;

    倍增法构造后缀数组,使用基数排序。基数排序在后缀数组中可以在O(n)的时间内对一个二元组(p,q)进行排序,其中p是第一关键字,q是第二关键字

    我们把每个后缀分开来看。

    开始时,每个后缀的第一个字母的大小是能确定的,也就是他本身的ASCLL值

    具体点?把第ii个字母看做是(s[i],i)的二元组,对其进行基数排序

    这样我们就得到了他们的在完成第一个字母的排序之后的相对位置关系

    sa[i]:排名为i的后缀的位置

    rak[i]:从第i个位置开始的后缀的排名,下文为了叙述方便,把从第i个位置开始的后缀简称为后缀i

    tp[i]:基数排序的第二关键字,意义与sa一样

    tax[i]i号元素出现了多少次。辅助基数排序

    s[i]:字符串

    “倍增法”,每次将排序长度*2,最多需要log(n)次便可以完成排序

    因此我们现在需要对每个后缀的前两个字母进行排序

    此时第一个字母的相对关系我们已经知道了。

    由于第i个后缀的第二个字母,实际是第i+1个后缀的第一个字母

    因此每个后缀的第二个后缀的字母的相对位置关系我们也是知道的。

    我们用tp这个数组把他记录出来,对rak,tp这个二元组进行基数排序

    接下来我们需要对每个后缀的前四个后缀进行排序

    此时我们已经知道了每个后缀前两个字母的排名,而第i个后缀的第3,4个字母恰好是第i+2个后缀的前两个字母。

    他们的相对位置我们又知道啦。

    这样不断排下去,最后就可以完成排序啦

    举个栗子,banana先按第一个字母排序

    然后给前两个字母排序,也就是把相邻二元组合并。再根据字典序排

    再排前四个

     

    最长公共前缀(LCP)

    对两个字符串u,v 定义函数lcp(u,v)=max{i|u=iv},对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]),其中i,j 均为1 至n 的整数。

    LCP(i,j)也就是后缀数组中第i 个和第j 个后缀的最长公共前缀的长度。

    关于LCP 有两个显而易见的性质:

    性质2.1 LCP(i,j)=LCP(j,i)

    性质2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1

    这两个性质的用处在于,我们计算LCP(i,j)时只需要考虑i<j 的情况,因为i>j时可交换i,j,i=j时可以直接输出结果n-SA[i]+1。

    并且LCP有一些定理【证明见OI2004国家集训队论文《后缀数组》许智磊,链接附在文后】

    Lemma: 对任意1≤i<j<k≤n,LCP(i,k)=min{LCP(i,j),LCP(j,k)}

    LCP Theorem: LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} 

    LCP Corollary 对 i≤j<k,LCP(j,k)≥LCP(i,k)

     

    定义数组height,height[i] = LCP(i-1, i),那么根据定理可得LCP(i,j)=min{height[k]|i+1≤k≤j}

    那么求LCP的问题就可以变成经典的RMQ问题【如果height是固定的】,可以用线段树来维护。

    【论文中提到的RMQ标准算法,O(n)时间预处理,O(1)完成查询,太菜,不会。】

    设i<n,j<n,Suffix(i)和Suffix(j)满足lcp(Suffix(i),Suffix(j)>1,则成立以下两点:

    Fact 1 Suffix(i)<Suffix(j) 等价于Suffix(i+1)<Suffix(j+1)。

    Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。

     

    那么如何高效的求height数组?

    为了描述方便,设h[i]=height[Rank[i]],即height[i]=h[SA[i]]。

    h 数组满足一个性质:对于i>1 且Rank[i]>1,一定有h[i]≥h[i-1]-1。

    根据这个性质,可以令i从1 循环到n按照如下方法依次算出h[i]:

    若 Rank[i]=1,则h[i]=0。字符比较次数为0。

    若 i=1 或者h[i-1]≤1,则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同,由此计算出h[i]。字符比较次数为h[i]+1,不超过h[i]-h[i-1]+2。

    否则,说明i>1,Rank[i]>1,h[i-1]>1,根据性质3,Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1 个字符是相同的,于是字符比较可以从h[i-1]开始,直到某个字符不相同,由此计算出h[i]。字符比较次数为h[i]-h[i-1]+2。

    求出了h 数组,根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组,于是可以在O(n)时间内求出height 数组。

     

    kuangbin的模板

    复制代码
     1 /*
     2 *suffix array
     3 *倍增算法  O(n*logn)
     4 *待排序数组长度为n,放在0~n-1中,在最后面补一个0
     5 *build_sa( ,n+1, );//注意是n+1;
     6 *getHeight(,n);
     7 *例如:
     8 *n   = 8;
     9 *num[]   = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0,其他大于0
    10 *rank[]  = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值,rank[n]必定为0无效值
    11 *sa[]    = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值,sa[0]必定为n是无效值
    12 *height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
    13 *
    14 */
    15 
    16 int sa[MAXN];//SA数组,表示将S的n个后缀从小到大排序后把排好序的
    17              //的后缀的开头位置顺次放入SA中
    18 int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量,不需要赋值
    19 int rank[MAXN],height[MAXN];
    20 //待排序的字符串放在s数组中,从s[0]到s[n-1],长度为n,且最大值小于m,
    21 //除s[n-1]外的所有s[i]都大于0,r[n-1]=0
    22 //函数结束以后结果放在sa数组中
    23 void build_sa(int s[],int n,int m)
    24 {
    25     int i,j,p,*x=t1,*y=t2;
    26     //第一轮基数排序,如果s的最大值很大,可改为快速排序
    27     for(i=0;i<m;i++)c[i]=0;
    28     for(i=0;i<n;i++)c[x[i]=s[i]]++;
    29     for(i=1;i<m;i++)c[i]+=c[i-1];
    30     for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    31     for(j=1;j<=n;j<<=1)
    32     {
    33         p=0;
    34         //直接利用sa数组排序第二关键字
    35         for(i=n-j;i<n;i++)y[p++]=i;//后面的j个数第二关键字为空的最小
    36         for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
    37         //这样数组y保存的就是按照第二关键字排序的结果
    38         //基数排序第一关键字
    39         for(i=0;i<m;i++)c[i]=0;
    40         for(i=0;i<n;i++)c[x[y[i]]]++;
    41         for(i=1;i<m;i++)c[i]+=c[i-1];
    42         for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
    43         //根据sa和x数组计算新的x数组
    44         swap(x,y);
    45         p=1;x[sa[0]]=0;
    46         for(i=1;i<n;i++)
    47             x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
    48         if(p>=n)break;
    49         m=p;//下次基数排序的最大值
    50     }
    51 }
    52 void getHeight(int s[],int n)
    53 {
    54     int i,j,k=0;
    55     for(i=0;i<=n;i++)rank[sa[i]]=i;
    56     for(i=0;i<n;i++)
    57     {
    58         if(k)k--;
    59         j=sa[rank[i]-1];
    60         while(s[i+k]==s[j+k])k++;
    61         height[rank[i]]=k;
    62     }
    63 }
    复制代码

     

    参考链接:

    后缀树 https://www.cnblogs.com/gaochundong/p/suffix_tree.html

    后缀数组 https://www.cnblogs.com/gaochundong/p/suffix_array.html

    https://www.douban.com/note/210945706/

    https://www.cnblogs.com/jinkun113/p/4743694.html

    OI2004国家集训队论文《后缀数组》许智磊https://github.com/Booooooooooo/OI-Public-Library/blob/master/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%871999-2017/2004/%E8%AE%B8%E6%99%BA%E7%A3%8A.pdf

     OI2009国家集训队论文《后缀数组——处理字符串的有力工具》https://github.com/Booooooooooo/OI-Public-Library/blob/master/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%871999-2017/2009/%E7%BD%97%E7%A9%97%E9%AA%9E/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%A4%84%E7%90%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%9C%89%E5%8A%9B%E5%B7%A5%E5%85%B7.pdf

    展开全文
  • 基于概率后缀树的时空轨迹位置预测,李萍,孙礼,近年来,移动对象的位置预测引起了广大研究人员的关注。传统的位置预测算法主要考虑移动对象在空间上的转移规律,而忽略了历史轨��
  • 后缀树的构造方法-Ukkonen详解
  • 后缀树总结-java版

    2019-04-22 16:00:27
    后缀树简介 字典树(前缀树)的概念 后缀树的概念 构造后缀树 两种方法在平方时间内构件后缀树 线性时间建立后缀树的理论 直接在后缀树上操作  自动更新叶节点 当新后缀出现在原先后缀树中 线性时间建立...
  • 计算机病毒检测中基于概率后缀树模型的分类方法研究,张丹辉,付垒朋,本文研究在Windows平台下基于概率后缀树检测PE病毒的具体方法。首先,利用IDA工具在Windows平台的虚拟机环境下提取系统API调用序列,基��
  • 后缀自动机构造后缀树

    千次阅读 2018-07-12 23:23:52
    那么 将串复制一遍 然后在反过来建sam就可以得到后缀树 然后后缀树就是精简之后的后缀trie所以我们在后缀trie上dp可以得到同样的效果 因为这题我们边上只有一种对应的情况所以我们总能赢所以预处理一下能赢的前缀和 ...
  • “一棵树就是一棵树。你还要看多少?” ——罗纳德·里根 并发树 该项目为Java提供并发和并发。 概述 基数树(也称为 patricia trie、...后缀树(也称为 PAT 树或位置树)是基数树的扩展,它允许将键的后缀插入树中

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,589
精华内容 28,635
关键字:

后缀树