精华内容
下载资源
问答
  • 2022-05-18 09:36:19

    作者:20.4 隋春雨

    1. 概述
      后缀树,就是把一串字符的所有后缀保存并且压缩的字典树。相对于字典树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串等等。
      性质:一个字符串构造了一棵树,树中保存了该字符串所有的后缀。
      操作:就是建立和应用。
      (1)建立后缀树
      比如单词banana,它的所有后缀显示到下面的。0代表从第一个字符为起点,终点不用说都是字符串的末尾。
      以上面的后缀,我们建立一颗后缀树。如下图,为了方便看到后缀,我没有合并相同的前缀。
      在这里插入图片描述
      前面简介的时候我们说了,后缀树是把一个字符串所有后缀压缩并保存的字典树。所以我们把字符串的所有后缀还是按照字典树的规则建立,就成了下图的样子。这就是后缀树的压缩,可见更加节省空间。
      在这里插入图片描述
      在这里插入图片描述
      注意还是和字典树一样,根节点必须为空。
    2. 后缀树的应用
      后缀树能解决大多数字符串的问题
      (1)查找某个字符串s1是否在另外一个字符串s2中。这个很简单,如果s1在字符串s2中,那么s1必定是s2中某个后缀串的前缀。理解以下后缀串的前缀这个词,其实每个后缀串也就是起始地点不同而已,前缀也就是从开头开始结尾不定。后缀串的前缀就可以组合成该原先字符串的任意子串了。比如banana,anan是anana这个后缀串的前缀。
      (2)指定字符串s1在字符串s2中重复的次数
      比如说banana是s1,an是s2,那么计算an出现的次数实际上就是看an是几个后缀串的前缀。上图的a节点是保存所有起始为a字母的后缀串,我们看a字母后的n字母的引用计数即可。
      (3)两个字符串S1,S2的最长公共部分(广义后缀树)
      (4)最长回文串(广义后缀树)
      详细介绍见博客从Trie树(字典树)谈到后缀树

    后缀树(Suffix tree):
    :一个具有m个词的字符串S的后缀树T,就是一个包含一个根节点的有向树,该树恰好带有m个叶子,这些叶子被赋予从1到m的标号。 每一个内部节点,除了根节点以外,都至少有两个子节点,而且每条边都用$的一个非空子串来标识。出自同一节点的任意两条边的标识不会以相同的词开始。后缀树的关键特征是:对于任何叶子i,从根节点到该叶子所经历的边的所有标识串联起来后恰好拼出S的从i位置开始的后缀,即S[i,…,m]。树中节点的标识被定义为从根到该节点的所有边的标识的串联。

    后缀:一个长度为m的字符串序列S=s1 s2 ....sm,记Si=si si+1 .....sm为S的第 i 个后缀,显然S1=S 为原来的字符串;

    后缀树的定义:长度为m的序列S,其后缀树是一个有向树,满足以下条件:

    1)有m个叶结点; 2)除了根结点和叶结点,每一个内部结点至少有两条边(子节点),每条边对应S中的一个非空序列;

    3)从任何一个内部结点出发的两条边对应的字符串序列的第一个字符都不相同;

    4)从根结点到叶结点的路径上的字符序列构成了S从i开始的一个后缀字符串;

    路径标签:一个路径上对应的字符序列称为路径标签;

    结点标签:从根结点开始到此结点对应的路径的标签称为结点标签;

    并不是所有的字符序列都有后缀树,例如xabxa(其后缀有xabxa,abxa,bxa,xa,a)xa为xabxa的前缀,为了解决此问题,通常在字符串末尾加上$符号,使得任何一个后缀都不为其他后缀的前缀。

    (xabxa$的后缀树)

     注:从根结点到叶子结点路径上的字符(词)表示对应叶节点 i 开始的某一个后缀字符串,叶子结点存储了起始位置 i 有几个字符(词)就有几个叶子结点,根结点和内部结点不存储任何数据,只有叶子结点和边存储数据;

    隐含后缀树:序列S的隐含后缀树是指,序列S$的后缀树,去掉那些有$的边的$符号,之后将空边删除所得到的树;

    (xabxa$的隐含后缀树)

    即:隐含后缀树构造即删除所有边的$符号之后将空边删除;

    后缀树的构造:
    根据S字符串的前缀s1 s2....si构造隐含后缀树Ti,当i=m时即可构造出S的隐含后缀树;

    后缀树伪代码
    1、初始化一个隐含后缀树
    for i 从 1 到 m:  //m为字符串长度
       逐步构造隐含后缀树
       for j 从 1 到 i+1:
            #后缀拓展规则
            在已经构建好的后缀树中找到从root结点出发
            标记位S[j....i]的序列,如果需要的话将
            S[i+1]加入到这条路径后面
       进行下一次隐含后缀树的构造
    end  //完成整个后缀树的构造
    后缀的扩展规则:

    令β=S【j....i】,这里的β为S【1....i】的某一个后缀,第j步扩展是为了保证序列β,S【i+1】在树中;

    1、规则1:路径β是以一个叶子结点结尾的只需将S【i+1】直接加入在叶子结点上面;

    (路径β以一个叶子结点为结束,直接在此路径上增加一个S【i+1】)

    2、规则2:路径β后面没有以S【i+1】开始,但至少有一个路径是β的延续,如果β终止于内部结点则新建一个叶子结点

    作为这个内结点的子结点并将此边标记为S【i+1】,当β是在一条边的中间时除了建立一个子结点外还要建立一个从根结点

    出发标记为β的内部结点。

    (路径β在中间部分则从其末尾插入一个内部结点以及生成这个内部结点的子结点其路径标记为S【i+1】)

    3、规则3:有某个路径是β的末端开始且S【i+1】开头则无需进行任何操作;

    (有以β开头的路径什么也不做)

    例子:字符串S=“axabxb“的后缀树的逐步构建;

    字符    a    x    a    b    x    b
    下标    1    2    3    4    5    6


     时间复杂度分析:

    对于内层循环每一次都要寻找一条路径β,其时间复杂度为O(β)内外层循环为O(i^2),合起来时间复杂度为O(m^3);

    更多相关内容
  • 后缀树代码

    2017-08-20 21:57:33
    后缀树及其相关功能(如找最大子串等),参考https://www.oschina.net/translate/ukkonens-suffix-tree-algorithm-in-plain-english网站的UKKonen算法讲解(较易理解)与...abacabdabcdacad等
  • C语言数据结构之中缀树转后缀树的实例 对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢? 网上关于这方面的资料...
  • 后缀树

    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++实现

    2018-05-27 23:04:07
    本压缩文件是关于后缀树的,包括后缀树的构建(采用Ukkonen算法),利用构建的后缀树进行字符串的查找。
  • 在时间序列符号化基础上,本文引入概率后缀树 PST 模型,构建基于时间序列符号 化和概率后缀树相结合的股票预测模型.本文选择在沪深300的10支股票数据上将预测模型与传统的马尔科夫模型 MM 和自回归移动...
  • java后缀树代码

    2019-05-24 02:02:02
    NULL 博文链接:https://ganting.iteye.com/blog/371728
  • 后缀树 构建算法

    2019-04-05 01:08:20
    NULL 博文链接:https://ytrgmj.iteye.com/blog/1513687
  • 为了便于用户浏览搜索引擎产生的搜索结果,结H-合STC算法和变色龙算法提出了一种中文网页的层次聚类方法-STCC算法。该方法采用雅可比系数修改了STC算法中基本类相似度的计算方法,然后根据基本类相似度矩阵,利用...
  • 字符串树后缀 实现后缀树以在文本中搜索模式。
  • 前缀树和后缀树

    2018-10-31 20:04:45
    转自:从Trie树(字典树)谈到后缀树 引言 谈及Tire树与后缀树之前,先看俩个问题: **第一个问题:**一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度...

    转自:从Trie树(字典树)谈到后缀树

    引言

    谈及Tire树与后缀树之前,先看俩个问题:
    **第一个问题:**一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
    其中,海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用trie树统计每个词出现的次数,时间复杂度是O(nle)(le表示单词的平均长度),然后是找出出现最频繁的前10个词。也可以用堆来实现(具体的操作可参考第三章、寻找最小的k个树),时间复杂度是O(nlg10)。所以总的时间复杂度,是O(nle)与O(nlg10)中较大的一个。

    **第二个问题:**找出给定字符串里的最大回文。例子:输入 XMADAMYX, 则输出MADAM。这道题流行解是用后缀树(Suffix Tree), 其实在做LeetCode中最大回文的时候,用了动态规划。当然后缀树(Suffix Tree)的用途不仅如此,它高效的解决一大票复杂的字符串编程问题(当然也有弱点,如算法实现复杂及空间开销大),概括如下:

    • 查询字符串是否包含子串S1。只要思想:如果S包含S1,那么S1必定是S的某个后缀的前缀;又因为S的后缀树包含了所有的后缀,所以只需要对S的后缀树使用和Trie相同的查找方法查找S1即可(使用后缀树实现的复杂度同流行的KMP算法的复杂度相当)。
    • 找出字符串S的最长重复子串S1。比如abcdabcefda里abc和da都重复出现,而最大重复子串是abc。
    • 找出字符串S1同S2的最长公共子串。注意最长公共子串 (Longest CommonSubstring)和最大公共子序列(LongestCommon Subsequence, LCS)的区别: 子串(Substring) 是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的顺序,而从序列中去掉任意的元素而获得的新序列;更简略地说,前者(子串)的字符的位置必须连续,后者(子序列LCS)则不必。比如字符串acdfg同akdf的最长公众子串为df,而他们的最长公共子序列是adf。LCS可以使用动态规划去解决。
    • Ziv-Lampel无损压缩算法。LZW算法的基本原理是利用编码数据本身存在字符串重复特性来实现数据压缩,所以一个很好的选择是使用后缀树的形式来组织存储字符串及其对应压缩码值的字典。
    • 找出字符串S的最长回文字串S1。例如: XMADAMYX的最长回文子串是MADAM(此即为上面所说的第二个问题:最长回文问题)。
    • 多模式串的模式匹配问题。(suffix_array + 二分)

    本文第一部分,咱们就来了解这个Trie树,然后自然而然过渡到第二部分、后缀树,接着进入第三部分、详细阐述后缀树的构造方法-Ukkonen,最后第四部分、对自动机,KMP算法,Extend-KMP,后缀树,后缀数组,trie树,trie图及其应用做个全文概括性总结。

    第一部分、Trie树

    1.1 什么是Trie树

    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不限于字符串),所以经常被搜索引擎用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
    它有3个基本的性质:
      1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
      2. 从根节点到某一节点,路径上经过的字符连起来,为该节点对应的字符串。
      3. 每个节点的所有子节点包含的字符都不相同。

    1.2 树的构建

    题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。
    分析:这题当然可以用hash来解决,但是本文重点介绍的是Trie树,因为在某个方面它的用途更大。比如对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用Trie树还是很简单的。
      现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。
      好比假设有b, abc, abd, bcd, abcd, efg, hii这6个单词,我们构建的树就是如下图所示的:
      在这里插入图片描述
      从上图便可窥之一二,好比大海搜人,立马就能确定东西南北中的到底哪个方位,如此迅速缩小查找的范围和提高查找的针对性,不失为一创举。
      如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。那么,对于一个单词,我们只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
      这样一来我们查询和插入就可以一起完成,所以时间仅仅为单词长度,在这一个样例,便是10。
      我们可以看到,Tire树每一层的节点数是26^i级别的。所以为了节省空间,我们用动态链表,或者用数组来模拟动态。空间的花费,不会超过单词数*单词长度。

    1.3 树的构建

    上文中提到”比如说对于某一个单词,我们要询问它的前缀是否出现过,这样hash就不好搞了,而用Trie还是很简单”。下面,我们看看这个前缀查询问题。

    ---问题: 已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串下面对比3种方法:---

    • 1.最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。
    • 2.使用hash: 我们用hash存下所有字符串的所有的前缀子串,建立存有子串hash的复杂度为O(n*len),而查询的复杂度为O(n)*O(1)=O(n)。
    • 3.使用Trie:因为当查询如字符串abc是否为某个字符的前缀时候,显然以b,c,d…等不是以a开头的字符串就不用查找了。所以建立Trie的复杂度为O(nlen), 而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(nlen),实际查询的复杂度也只是O(len)。(说白了,就是Trie树的平均高度h为len,所以Trie树的查询复杂度为O(h)=O(len)。好比一棵二叉平衡树的高度为logN,则其查询,插入的平均时间复杂度亦为O(logN))

    下面解释下上述方法3中所说的为什么hash不能将建立与查询同时执行,而Trie树却可以:

    • 在hash中,例如现在要输入两个串911,911456,如果要同时查询这两个串,且查询串的同时若hash中没有则存入。那么,这个查询与建立的过程就是先查询其中一个串911,没有,然后存入9、91、911;而后查询第二个串911456,没有然后存入9、91、911、9114、91145、911456。因为程序没有记忆功能,所以并不知道911在输入数据中出现过,只是照常以例行事,存入9、91、911、9114、911…。也就是说用hash必须先存入所有子串,然后for循环查询。
    • 而trie树中,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时,当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀。

    1.4查询

    Trie树是简单但实用的数据结构,通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时,就是Trie开始。本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面,再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:
    在这里插入图片描述
    可以看出:

    • 每条边对应一个字母。
    • 每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。
    • 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

    查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。

    搭建Trie的基本算法也很简单,无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:

    • 考察前缀"a",发现边a已经存在。于是顺着边a走到节点a
    • 考察剩下的字符串"dd"的前缀"d",发现从节点a出发,已经有边d存在。于是顺着边d走到节点ad
    • 考察最后一个字符"d",这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边ad->add标记为d。

    1.5 Trie树的应用

    除了本文引言所述的问题能应用Trie树解决之外,Trie树还能解决下述问题(节选至:,海量数据处理面试题集锦与Bit-map详解):

    • 有一个1G大小的文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
    • 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现呢?
    • 一个文本文件,大约有1万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
    • 寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询的重复度比较高,虽然总数是1千万,但是如果去除重复的,不超过300万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不超过1G。
      (1)请描述你解决这个问题的思路。
      (2)请给出主要的处理流程,算法,以及算法的复杂度。

    第二部分、后缀树

    2.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[0…7], XMADAMYX, 也就是字符串本身,起始位置为0
    S[1…7], MADAMYX,起始位置为1
    S[2…7], ADAMYX,起始位置为2
    S[3…7], DAMYX,起始位置为3
    S[4…7], AMYX,起始位置为4
    S[5…7], MYX,起始位置为5
    S[6…7], YX,起始位置为6
    S[7…7], X,起始位置为7
    空字串,记为$
    而后缀树,就是包含一则字符串所有后缀的压缩Trie。把上面的后缀加入Trie后,我们得到下面的结构:
    在这里插入图片描述
    仔细观察上图,我们可以看到不少值得压缩的地方。比如蓝框标注的分支都是独苗,没有必要用单独的节点同边表示。如果我们允许任意一条边包含多个字母,就可以把这种没有分叉的路径压缩到一条边。另外每条边已经包含了足够的后缀信息,我们就不用再给节点标注字符串信息了。我们只需要叶节点上标注上每项后缀的起始位置。于是得到下图:
    在这里插入图片描述
    这样的结构丢失了某些后缀。比如后缀X在上面消失了,因为它正好是字符串XMADAMYX的前缀。为了避免这种情况,我们也规定每项后缀不能是其他后缀的前缀。 要解决这个问题其实很简单,在待处理的子串后加一个空字串就行了。例如我们处理XMADAMYX前,先把XMADAMYX变为XMADAMYX$,于是就得到suffix tree–后缀树了,如下图所示:
    在这里插入图片描述

    2.2. 后缀树的定义

    那后缀树同最长回文有什么关系呢?我们得知道俩个概念:

    1. 最低共有祖先,LCA(Lowest Common Ancestor),也就是任意俩节点(多个也行)最长的共有前缀。比如下图,节点7同节点1的共同祖先是节点5和节点10,但最低共有祖先是5。查找LCA的算法是O(1)的复杂度,当然,代价是需要对后缀树做复杂度为O(n)的预处理。
      在这里插入图片描述

    2. 广义后缀树(Generalized Suffix Tree)。传统的后缀树处理一坨单词的后缀。广义后缀树存储任意多个单词的所有后缀。例如下图是单词XMADAMYXXYMADAMX的广义后缀树。注意我们需要区分不同单词的后缀,所以叶节点用不同的特殊符号与后缀位置配对。
      在这里插入图片描述

    2.3、最长回文问题的解决

    有了上面的概念,本文引言提出的查找回文问题就相对简单了。咱们来回顾下引言中提出的回文问题的具体描述:找出指定字符串里的最长回文。例如输入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。有了这套直观解释,算法自然呼之欲出:
    预处理后缀树,使得查询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)。

    用上图做例子,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。

    2.4、后缀树的应用

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

    -查找字符串o是否在字符串S中。
    方案:用S构造后缀树,按在trie中搜索字串的方法搜索o即可。
    原理:若o在S中,则o必然是S的某个后缀的前缀。
    例如S: leconte,查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提,采用trie搜索的方法
    就不难理解了。

    • 指定字符串T在字符串S中的重复次数。
      方案:用S+’$'构造后缀树,搜索T节点下的叶节点数目即为重复次数
      原理:如果T在S中重复了两次,则S应有两个后缀以T为前缀,重复次数就自然统计出来了。

    • 字符串S中的最长重复子串
      方案:原理同2,具体做法就是找到最深的非叶节点。
      这个深是指从root所经历过的字符个数,最深非叶节点所经历的字符串起来就是最长重复子串。
      为什么要非叶节点呢?因为既然是要重复,当然叶节点个数要>=2。

    • 两个字符串S1,S2的最长公共部分
      方案:将S1#S2KaTeX parse error: Expected 'EOF', got '#' at position 32: …非叶节点,且该节点的叶节点既有#̲也有(无#)。

    剩下部分后缀树的构造方法-Ukkonen归纳反思优化 请见原文 https://blog.csdn.net/v_july_v/article/details/6897097

    展开全文
  • 后缀树构造与应用

    2017-08-20 22:00:42
    关于后缀树Ukkonen算法的解释,以https://www.oschina.net/translate/ukkonens-suffix-tree-algorithm-in-plain-english网站讲解为基础
  • “一棵树就是一棵树。你还要看多少?” ——罗纳德·里根 并发树 该项目为Java提供并发和并发。 概述 基数树(也称为 patricia trie、...后缀树(也称为 PAT 树或位置树)是基数树的扩展,它允许将键的后缀插入树中
  • 字符串-后缀树和后缀数组详解

    千次阅读 2021-05-15 16:17:16
    后缀树和后缀数组可以解决大部分字符串问题。光速从入门到放弃,看这一篇就够了。 例题: HDU-1403最长公共子串 洛谷P2408 不同子串个数 HDU-5769Substring

    在这里插入图片描述

    后缀树


    建议先了解一下字典树

    首先理解后缀的概念,后缀(suffix)即从某个位置开始到末尾的一个子串。例如字符串 s = a a b a b s=aabab s=aabab,它的五个后缀为 a a b a b aabab aabab a b a b abab abab b a b bab bab a b ab ab b b b

    后缀树(suffix tree)就是把所有的后缀子串用字典树的方法建立的一棵树,如图:
    在这里插入图片描述
    其中根节点为空,还可以在叶子节点后用一个’$'符标识结束,从根节点出发就能到达所有的子串情况。

    模板:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100005;
    int trie[maxn][26];
    int pos = 1, n;
    char s[maxn], t[maxn];
    void insert(int idx) { //构建后缀树
        int p = 0; 
        for (int i = idx; i < n; i++) {
            int u = s[i] - 'a';
            if (trie[p][u] == 0)
                trie[p][u] = pos++;
            p = trie[p][u];
        }
    }
    bool find() {  //查询是否是子串
        int p = 0;
        for (int i = 0; s[i]; i++) {
            int u = s[i] - 'a';
            if (trie[p][u] == 0)
                return false;
            p = trie[p][u];
        }
        return true;
    }
    int main() {
        scanf("%s%s", s,t);
        n = strlen(s);
        for (int i = 0; i < n; i++) {//枚举起点
            insert(i);
        }
        printf("%s子串", find() ? "是" : "不是");
        return 0;
    }
    

    但是不难发现,建树的时间和空间成本都很高。后缀数组和后缀自动机可以看作是对后缀树时间和空间上的优化,通过映射关系避免建树和提高树节点重复利用率。

    后缀数组


    概念

    直接对后缀树构造和编程不太方便,而后缀数组(suffix array)就是更简单的替代方法。

    下标i后缀s[i]下标j字典序后缀数组sa[j]
    0aabab0aabab0
    1abab1ab3
    2bab2abab1
    3ab3b4
    4b4bab2

    后缀数组就是字典序对应的后缀下标,即 s a sa sa(suffix array缩写)数组。比如 s [ 1 ] = 3 s[1]=3 s[1]=3,表示字典序排1的子串,是原来字符串中第3个位置开始的后缀子串,即 a b ab ab

    通过后缀数组能方便的解决一些字符串问题,如在母串 s s s中查找子串 t t t,只需在 s a [ ] sa[] sa[]上做二分搜索,时间复杂度是 O ( m l o g n ) O(mlogn) O(mlogn),m子串长度n母串长度,如查找 b a ba ba

    #include<bits/stdc++.h>
    using namespace std;
    string s, t;
    int sa[] = { 0,3,1,4,2 }; //设sa[]已求出
    int find() {  //t在s中位置
        int l = 0, r = s.size();
        while (r > l + 1) { //字典序里二分
            int mid = (l + r) / 2;
            if (s.compare(sa[mid], t.length(), t) < 0)
                l = mid;  //-1不相等移动左指针
            else r = mid; //0相等移动右指针
        }
        if (s.compare(sa[r], t.length(), t) == 0)
            return sa[r];  //返回原始位置
        if (s.compare(sa[l], t.length(), t) == 0)
            return sa[l];
        return -1; //没找到
    }
    int main() {
        s = "aabab";
        t = "ba";
        cout << find();
        return 0;
    }
    

    sa[]

    那现在的问题是如何高效的求后缀数组 s a [ ] sa[] sa[],即对后缀子串进行排序?

    若直接使用快排,每两个字符串间还有 O ( n ) O(n) O(n)的比较,所以总的复杂度是 O ( n 2 l o g n ) O(n^2logn) O(n2logn),显然不够友好。答案是使用倍增法

    1. 用数字替代字母,如a=0,b=1。
    2. 连续两个数字组合,如00代表aa,01代表ab,最后一个1没有后续,在尾部加上0,组成10,并不影响字符得比较。
    3. 连续4个数字组合,如0010代表aaba,同样得01和10没有后续,补0。
    4. 得到5个完全不一样的数字,可以区分大小了,进行排序,得到rk数组={0,2,4,1,3}。
    5. 最后通过排名得到后缀数组sa[]={0,3,1,4,2}。
    步骤aabab
    第一步00101
    第二步0001100110
    第三步00100101101001001000
    下标i01234
    排序rk[i]02413
    转换sa[i]sa[0]=0sa[2]=1sa[4]=2sa[1]=3sa[3]=4
    sa[i]03142

    上述每一步递增两倍,总共 l o g ( n ) log(n) log(n)步,但是当字符串很长时,产生的组合数字就非常大可能溢出,这时就需要每一步都进行一个压缩,只要相对顺序不变即可,如下:

    步骤aabab
    第一步00101
    第二步0001100110
    排序rk[]01212
    第三步0211221020
    下标i01234
    排序rk[i]02413
    转换sa[i]sa[0]=0sa[2]=1sa[4]=2sa[1]=3sa[3]=4
    sa[i]03142

    rk[]

    也就是说求后缀数组 s a [ ] sa[] sa[],需要通过一个排名 r k [ ] rk[] rk[]来求。两者是一一对应的关系,互为逆运算,可以互相推导,即 s a [ r k [ i ] ] = i sa[rk[i]]=i sa[rk[i]]=i r k [ s a [ i ] ] = i rk[sa[i]]=i rk[sa[i]]=i

    • sa[]后缀数组,suffix array缩写,记录的是位置,是字典序排名第i的是谁。
    • rk[]排名数组,rank array缩写,记录的是排名,是第i个后缀子串排名第几。

    那得到倍增后的相对大小数字后,我们可以直接用快排 s o r t ( ) sort() sort()得到 r k [ ] rk[] rk[],每次快排 O ( n l o g n ) O(nlogn) O(nlogn),需要快排 l o g ( n ) log(n) log(n)次,总复杂度是 O ( n ( l o g n ) 2 ) O(n(logn)^2) O(n(logn)2)
    模板:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 200005;
    char s[maxn];
    int sa[maxn], rk[maxn], tmp[maxn + 1];
    int n, k;
    bool cmp_sa(int i, int j) { //直接比较,省去组合过程
        if (rk[i] != rk[j]) //比较组合数高位
            return rk[i] < rk[j];
        else { //比较组合数低位
            int ri = i + k <= n ? rk[i + k] : -1;
            int rj = j + k <= n ? rk[j + k] : -1;
            return ri < rj;
        }
    }
    void calc_sa() { //计算sa[](快速排序)
        for (int i = 0; i <= n; i++) {
            rk[i] = s[i]; //记录原始数值
            sa[i] = i; //记录当前排序结果
        }
        for (k = 1; k <= n; k *= 2) { //每次递增2倍
            sort(sa, sa + n, cmp_sa);
            //因为rk[]存在相同数,所以需要上一轮rk[]才能比较(即cmp_sa里)
            //所以不能直接赋给rk[],需要一个tmp[]周转
            tmp[sa[0]] = 0; 
            for (int i = 0; i < n; i++) //sa[]倒推组合数记录在tmp[]
                tmp[sa[i + 1]] = tmp[sa[i]] + (cmp_sa(sa[i], sa[i + 1]) ? 1 : 0);
            for (int i = 0; i < n; i++)
                rk[i] = tmp[i];
        }
    }
    int main() {
        memcpy(s, "aabab", 6);
        n = strlen(s);
        calc_sa();
        for (int i = 0; i < n; i++)
            cout << sa[i] << " ";
        // 0 3 1 4 2
        return 0;
    }
    

    除了直接用快排sort,还有一种更快的排序方式——基数排序,总复杂度只有 O ( n l o g n ) O(nlogn) O(nlogn),就是有题目卡这点时间,丧心病狂

    基数排序是先比较低位再比较高位,使用哈希的思路,对于该位相同的数字直接放到相应的格子里。如排序{82,43,67,52,91,40},先按个位排序得{40,91,82,52,43,67},再按十位排序得{40,43,52,67,82,91}以此类推。

    格子0123456789
    个位409182,524367
    十位40,4352678291

    模板:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 200005;
    char s[maxn];
    int sa[maxn], rk[maxn];
    int cnt[maxn], t1[maxn], t2[maxn];
    int n, k;
    void calc_sa() { //计算sa[](基数排序)
        int m = 127; //ASCLL范围
        int i, * x = t1, * y = t2;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
        for (k = 1; k <= n; k *= 2) {
            int p = 0; //利用长度k的排序结果对长度2k的排序
            for (i = n - k; i < n; i++)y[p++] = i;
            for (i = 0; i < n; i++)
                if (sa[i] >= k)y[p++] = sa[i] - k;
            for (i = 0; i < m; i++)cnt[i] = 0;
            for (i = 0; i < n; i++)cnt[x[y[i]]]++;
            for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
            for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)break;
            m = p;
        }
    }
    int main() {
        memcpy(s, "aabab", 6);
        n = strlen(s);
        calc_sa();
        for (int i = 0; i < n; i++)
            cout << sa[i] << " ";
        // 0 3 1 4 2
        return 0;
    }
    

    height[]

    h e i g h t [ ] height[] height[]是一个辅助数组,和最长公共前缀(Longest Common Prefix,LCP)相关。

    定义 h e i g h t [ i ] height[i] height[i] s a [ i − 1 ] sa[i-1] sa[i1] s a [ i ] sa[i] sa[i]的最长公共前缀长度。例如前面的 a a b a b aabab aabab中, s a [ 1 ] sa[1] sa[1]表示 a b ab ab s a [ 2 ] sa[2] sa[2]表示 a b a b abab abab,那么 h e i g h t [ 2 ] = 2 height[2]=2 height[2]=2

    用暴力的方法比较相邻的 s a [ ] sa[] sa[],复杂度是 O ( n 2 ) O(n^2) O(n2),下面给出复杂度为 O ( n ) O(n) O(n)的模板:

    void getheight(int n) { //n是字符串长度
        int k = 0;
        for (int i = 0; i < n; i++)
            rk[sa[i]] = i;
        for (int i = 0; i < n; i++) {
            if (k)k--;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
            height[rk[i]] = k;
        }
    }
    

    插播反爬信息 )博主CSDN地址:https://wzlodq.blog.csdn.net/

    例题


    利用后缀数组可以解决很多字符串解决题目,如:

    1. 在串 s s s中查找子串 t t t
      前面给出过代码,二分查找 s a [ ] sa[] sa[]即可。
    2. 在串 s s s中找最长重复子串
      h e i g h t [ ] height[] height[]数组中最大值就是最长重复子串长度,该最长重复子串
    3. 找串 s 1 s1 s1和串 s 2 s2 s2的最长公共子串
      在合并串 s 1 s1 s1和串 s 2 s2 s2为串 s 3 s3 s3,并在中间插入一个’$’,这样就转换成了找最大重复子串,但是需要判断对应 s a [ i ] sa[i] sa[i] s a [ i − 1 ] sa[i-1] sa[i1]是否分别属于’$'前后两个字符串。
    4. 找串s的最大回文子串
      一般用Manacher(马拉车)算法。

    HDU-1403最长公共子串

    HDU-1403 Longest Common Substring

    Given two strings, you have to tell the length of the Longest Common Substring of them.
    For example:
    str1 = banana
    str2 = cianaic
    So the Longest Common Substring is “ana”, and the length is 3.
    Input
    The input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case.
    Process to the end of file.
    Output
    For each test case, you have to tell the length of the Longest Common Substring of them.
    Sample Input
    banana
    cianaic
    Sample Output
    3

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 200005;
    char s[maxn];
    int sa[maxn], rk[maxn], height[maxn];
    int cnt[maxn], t1[maxn], t2[maxn];
    int n, k;
    void calc_sa() {
        int m = 127;
        int i, * x = t1, * y = t2;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
        for (k = 1; k <= n; k *= 2) {
            int p = 0;
            for (i = n - k; i < n; i++)y[p++] = i;
            for (i = 0; i < n; i++)
                if (sa[i] >= k)y[p++] = sa[i] - k;
            for (i = 0; i < m; i++)cnt[i] = 0;
            for (i = 0; i < n; i++)cnt[x[y[i]]]++;
            for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
            for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)break;
            m = p;
        }
    }
    void getheight(int n) {
        int k = 0;
        for (int i = 0; i < n; i++)
            rk[sa[i]] = i;
        for (int i = 0; i < n; i++) {
            if (k)k--;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
            height[rk[i]] = k;
        }
    }
    int main() {
        while (~scanf("%s", s)) {
            int len1 = strlen(s);
            s[len1] = '$';
            scanf("%s", s + len1 + 1);
            n = strlen(s);
            calc_sa();
            getheight(n);
            int ans = 0;
            for (int i = 1; i < n; i++) {
                if (height[i] > ans) {
                    if ((sa[i] < len1 && sa[i - 1] >= len1) || sa[i - 1] < len1 && sa[i] >= len1)
                        ans = height[i];
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    

    这题快排和基数排序差了近十倍的速度。
    在这里插入图片描述

    洛谷P2408 不同子串个数

    P2408 不同子串个数

    题目背景
    因为NOI被虐傻了,蒟蒻的YJQ准备来学习一下字符串,于是它碰到了这样一道题:
    题目描述
    给你一个长为N的字符串,求不同的子串的个数
    我们定义两个子串不同,当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。
    子串的定义:原字符串中连续的一段字符组成的字符串
    输入格式
    第一行一个整数N
    接下来一行N个字符表示给出的字符串
    输出格式
    一行一个整数,表示不一样的子串个数
    输入输出样例
    输入 #1
    5
    aabaa
    输出 #1
    11
    输入 #2
    3
    aba
    输出 #2
    5
    说明/提示
    请使用64位整数来进行输出
    (具体来说,C++和C选手请使用long long 类型,pascal选手请使用Int64)
    由于输入文件过大,请使用 高效的读入方法(具体的,c++和c选手请不要使用cin,pascal选手不需要管)
    对于30%的数据,N≤1000
    对于100%的数据,N≤105

    每个后缀 s a [ i ] sa[i] sa[i]产生了n- s a [ i ] sa[i] sa[i]个前缀,而产生的这些前缀中有 h e i g h t [ i ] height[i] height[i]个是重复的,也就是产生了 n − s a [ i ] − h e i g h t [ i ] n-sa[i]-height[i] nsa[i]height[i]个不同子串。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 200005;
    char s[maxn];
    int sa[maxn], rk[maxn], height[maxn];
    int cnt[maxn], t1[maxn], t2[maxn];
    int n, k;
    void calc_sa() {
        int m = 127;
        int i, * x = t1, * y = t2;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
        for (k = 1; k <= n; k *= 2) {
            int p = 0;
            for (i = n - k; i < n; i++)y[p++] = i;
            for (i = 0; i < n; i++)
                if (sa[i] >= k)y[p++] = sa[i] - k;
            for (i = 0; i < m; i++)cnt[i] = 0;
            for (i = 0; i < n; i++)cnt[x[y[i]]]++;
            for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
            for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)break;
            m = p;
        }
    }
    void getheight(int n) {
        int k = 0;
        for (int i = 0; i < n; i++)
            rk[sa[i]] = i;
        for (int i = 0; i < n; i++) {
            if (k)k--;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
            height[rk[i]] = k;
        }
    }
    int main() {
        scanf("%d%s", &n, s);
        n++;
        calc_sa();
        getheight(n);
        n--;
        ll ans = 0;
        for (int i = 1; i <= n; i++)
            ans += n - sa[i] - height[i];
        printf("%lld", ans);
        return 0;
    }
    

    HDU-5769Substring

    HDU-5769 Substring

    ?? is practicing his program skill, and now he is given a string, he has to calculate the total number of its distinct substrings.
    But ?? thinks that is too easy, he wants to make this problem more interesting.
    ?? likes a character X very much, so he wants to know the number of distinct substrings which contains at least one X.
    However, ?? is unable to solve it, please help him.
    Input
    The first line of the input gives the number of test cases T;T test cases follow.
    Each test case is consist of 2 lines:
    First line is a character X, and second line is a string S.
    X is a lowercase letter, and S contains lowercase letters(‘a’-‘z’) only.
    T<=30
    1<=|S|<=10^5
    The sum of |S| in all the test cases is no more than 700,000.
    Output
    For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the answer you get for that case.
    Sample Input
    2
    a
    abc
    b
    bbb
    Sample Output
    Case #1: 3
    Case #2: 3
    Hint
    In first case, all distinct substrings containing at least one a: a, ab, abc.
    In second case, all distinct substrings containing at least one b: b, bb, bbb.

    把后缀按照字典序排序后,相邻两个后缀的前缀一定是相同的(height数组纪录),那么就不用重复考虑了,记录里每个字母向后最近的目标字符出现的位置,所取前缀至少要包含这个字母。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 200005;
    char s[maxn];
    int sa[maxn], rk[maxn], height[maxn];
    int cnt[maxn], t1[maxn], t2[maxn];
    int n, k;
    void calc_sa() {
        int m = 127;
        int i, * x = t1, * y = t2;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
        for (k = 1; k <= n; k *= 2) {
            int p = 0;
            for (i = n - k; i < n; i++)y[p++] = i;
            for (i = 0; i < n; i++)
                if (sa[i] >= k)y[p++] = sa[i] - k;
            for (i = 0; i < m; i++)cnt[i] = 0;
            for (i = 0; i < n; i++)cnt[x[y[i]]]++;
            for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
            for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)break;
            m = p;
        }
    }
    void getheight(int n) {
        int k = 0;
        for (int i = 0; i < n; i++)
            rk[sa[i]] = i;
        for (int i = 0; i < n; i++) {
            if (k)k--;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
            height[rk[i]] = k;
        }
    }
    int main() {
        int t;
        scanf("%d", &t);
        for (int cs = 1; cs <= t; cs++) {
            char x[3];
            scanf("%s%s", x, s);
            n = strlen(s);
            n++;
            calc_sa();
            getheight(n);
            n--;
            int nex[maxn];
            int pos = n;
            for (int i = n - 1; i >= 0; i--) {
                if (s[i] == x[0])pos = i;
                nex[i] = pos;
            }
            ll ans = 0;
            for (int i = 1; i <= n; i++) {
                ans += n - max(nex[sa[i]], sa[i] + height[i]);
            }
            printf("Case #%d: %lld\n", cs, ans);
        }
        return 0;
    }
    

    原创不易,请勿转载本不富裕的访问量雪上加霜
    博主首页:https://wzlodq.blog.csdn.net/
    来都来了,不评论两句吗👀
    如果文章对你有帮助,记得一键三连❤

    展开全文
  • Js 后缀树 Js Suffix Trie 是一个后缀 trie 实现,最初是用编写的,但也可以使用 JavaScript 编译。 您可以安装来编译 CoffeeScript,使用或尝试在线转换器。 关于后缀尝试 后缀树(不要与后缀树混淆)以树状方式...
  • 基于概率后缀树的时空轨迹位置预测,李萍,孙礼,近年来,移动对象的位置预测引起了广大研究人员的关注。传统的位置预测算法主要考虑移动对象在空间上的转移规律,而忽略了历史轨��
  • 后缀树的应用

    2019-05-01 22:06:54
    在这一节中,我们将给出几个常见的后缀树的应用,并且你将会看到它与其他处理字符串的算法与数据结构(例如KMP算法,AC自动机等)之间的比较。后缀树是一个非常强大的处理字符串问题的工具,并且企图在这一节短篇幅...
  • 经典的后缀树入门,后缀树组稍后共享,从零开始学数据结构。
  • 在无线传感器网络中,分簇路由具有管理方便、高效节能、易于实现等特点,成为当前重点研究的路由算法。现有的典型分簇路由算法存在着簇首节点能耗分布不均,簇首节点与基站未采用最短路径,数据可能“绕道”传递等...
  • 后缀树 后缀树的实现。 如何运行: > ghci suffixTree.hs λ graph . SuffixTree.construct $ "cacao" (或您想要的任何其他字符串而不是“ cacao ”) 依赖关系 ( brew install graphviz ) ( cabal install ...
  • 后缀树系列三:后缀树的应用

    千次阅读 2018-05-06 14:41:59
    前面两篇转载的后缀树系列文章已经描述了后缀树的线性构建算法。创建后缀树的O(n)算法,除了1995年E. Ukkonen大幅简化的算法,还有Peter Weiner的73年年度最佳算法、Edward McCreight1976的改进算法、Juha Kärkkä...
  • 后缀树构建UKK算法,实现语言是c++,供学习使用。后缀树构建算法UKK_vs2008cpp实现
  • 后缀树 & 后缀数组

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

    千次阅读 多人点赞 2018-10-29 21:42:56
    后缀树后缀树,就是把一串字符的所有后缀保存并且压缩的字典树。   相对于字典树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,099
精华内容 31,239
关键字:

后缀树