精华内容
下载资源
问答
  • 后缀树与后缀数组

    千次阅读 2016-08-12 11:14:36
    后缀树后缀数组是字符串处理的两大神器,几乎可处理掉一切的字符串处理问题,但是在实际中,后缀数组后缀树更好写、好调,同时时间上也不差(常数很小),所以后缀数组绝对是OI竞赛之必备神器。

    后缀树和后缀数组是字符串处理的两大神器,几乎可处理掉一切的字符串处理问题,但是在实际中,后缀数组比后缀树更好写、好调,同时时间上也不差(常数很小),所以后缀数组绝对是OI竞赛之必备神器。

    后缀树,实际上就是一棵字典树。考虑将某个串S的所有后缀插到一棵Trie里,那么我们就得到了一棵后缀树。在这里,我们不会讲后缀树的构造,只会略微讲一点其的思想。
    在后缀树而言,匹配就变成一件易事了。考虑一个字符串匹配问题,如果我们要在一个串A中找很多个字符串B=b0,b1,b2,那么也只需建好A的后缀树,然后直接放就好了……
    另外,还有许多扩展应用,但在这里我就不细讲了。下面来讲后缀数组。
    同样将一个字符串S的所有后缀,按照字典序排序,那么我们就得到了后缀数组。也就是说,后缀数组的第i个正是字典序第i大的后缀的编号。
    好的,那么怎么构造呢?一种方法是从排序入手,由于字符串的比较是Θ(n)的,所以说再乘上排序的比较次数(如使用快排)nlog2n,那么总的时间复杂度就是O(n2log2n)
    但是,后缀有一些特殊的性质,可以帮我们优化排序。


    我们要用的方法,是倍增算法,如果,我们每一次比较的时候,并不比较整个后缀,而是每次只比较一部分
    首先,我们将每个后缀的第一个字符排序,做出第一轮的sa(也就是Suffix Array,后缀数组),然后排第二轮,这次排两个字符,相当于是给二元组排序。
    然后,我们开始排四个字符,注意到,由于4=2+2,所以实际上……我们如果利用上一轮的排名,比如我们搞出另一个rank,使rank(i)为第i个后缀的排名(可能重叠),然后,假设我们现在要排后缀j的前四个字符,那么我们将这四个字符拆开,我们就可以得到前面的两个字符和后面的两个字符。前面的两个字符的排名正好是rank(j),而后面的两个字符,则是后缀j+2的前两个字符,其的排名是rank(j+2)。另外,我们来顺便证明一个定理:将若干个长度相同(设都为k)的字符串中的一个(e)分成两段,长度分别为l|e|l,那么如果我们已知字符串e在所有字符串的前l的字符构成的串中的排名和剩下来|e|l个字符构成的串中的排名r1r2,那么整一个字符串的排名等价于二元组(r1,r2)的排名。证明很容易,我们只需要注意到两个二元组(a,b)(c,d)的比较规则是当ac时比较ac,而当a=c时比较bd,那么我们就能够看出,由于我们已经有了前面一段的排名,那么我们只需要比较排名,排名哪一个更前,哪一个的字典序就相应的越高;如果其前半段的排名相等,即字典序相等,那么其前半段是完全一样的,我们就可以忽略前半段,比较后半段的排名。仔细一想,我们就可以发现,上面给出的二元组的比较过程,和字典序的比较过程,是完全一样的!只不过,我们“已经比较”过某些东西了,所以不用再直接地比较两两间的字典序了。
    利用倍增算法和快速排序的结合,我们可以在log2n×Θ(nlog2n)=Θ(nlog22n)的时间内解决这个问题,代码也很短,五六行左右就好了。如果没有时间写其他的话,可以直接用sort()和倍增算法相对暴力地解决。
    但是,我们有更高效的算法。基数排序!!!


    在这里,我们可以先按照上一轮的结果将第二个关键字排成一个序(相同的不管它),然后按照这个顺序,排。注意,插入的顺序应当和我们预先排的顺序一样。也就是说,大概是下面这样:

    for (int i=0;i<n;++i){
        insert(num1[i],i);
    }

    然后我们再将放进去的二元组再按照桶的大小顺序取出来,放好顺序,基数排序就完成了。
    但是,光有构造远远不够,这样我们只能拥有两个数组(而且本质上相同)ranksa。我们还需要一个特殊的工具,这个工具叫做最长公共前缀。


    两个字符串S1S2的最长公共前缀Lcp(S1,S2)的定义为

    Lcp(S1,S2)=maxi=1min{|S1|,|S2|}{S1i|S1i=S2i}

    那么,我们可以很容易地发现,其实某两个后缀的最长公共前缀Lcp(Ssai,Ssaj)的值,实际上是mink=min{sai,saj}max{sai,saj}1Lcp(Sk,Sk+1)。证明很容易,首先显然地,mink=min{sai,saj}max{sai,saj}1Lcp(Sk,Sk+1)Lcp(Ssai,Ssaj)(相当于若干个公共前缀的公共部分,可能可以再长),另外若设p=mink=min{sai,saj}max{sai,saj}1Lcp(Sk,Sk+1)q=Lcp(Ssai,Ssaj),而q>p,那么可以推出矛盾,这里不证(篇幅太长了,公式太大了……)
    好吧,总之这个被证出来了,那么我们怎样快速地求出Lcp(Ssai,Ssai+1)呢?容易证明,

    Lcp(Ssai,Ssai+1)Lcp(Ssai,Ssai1)1

    那么我们就可以不断地用上一个的答案来求出一个下界,再暴力扩展,然后继续求出下一个答案了。最后再用RMQ一搞就好了。
    后缀数组的应用相当多,而且实现相对简洁(可能吧),只要多想想,几乎没什么是搞不定的……

    【P.S.】后缀数组还可以有各种扩展,比如后缀家族的各种数据结构:后缀树、后缀数组、后缀自动机、后缀仙人掌……所以,太多了……

    展开全文
  • 后缀树的定义 假定给定一个长度为m的字符串S(下标从1到m),S的后缀树T为一个有m个叶结点的有根树,其叶节点从1到m编号;除了根节点之外,每个内部结点至少有两个孩子;每条边上都标有S的一个非空子串;从同一个...

    后缀树的定义
    假定给定一个长度为m的字符串S(下标从1到m),S的后缀树T为一个有m个叶结点的有根树,其叶节点从1到m编号;除了根节点之外,每个内部结点至少有两个孩子;每条边上都标有S的一个非空子串;从同一个结点引出的任意两条边上标的字符串都不会以相同字符开始·(晚上提早熄灯,待填)

    展开全文
  • 后缀树在1973年被首次提出,当时叫做position tree,该算法能够在线性时间内构建后缀树.,几年之后,又有了另外一种不同的线性算法,这种新算法更加节省空间,可以说是对原来算法的大幅度优化。1995年,在此基础上...

    ————《高级数据结构》
    1。后缀树的简介
    后缀树在1973年被首次提出,当时叫做position tree,该算法能够在线性时间内构建后缀树.,几年之后,又有了另外一种不同的线性算法,这种新算法更加节省空间,可以说是对原来算法的大幅度优化。1995年,在此基础上提出了第一个能在线构建的后缀树,并且该算法以一种更加容易理解的方式呈现。在此之后对后缀树研究,主要是将其应用到不同场景后的变化,如对字符串的适应能力,在外部构建(即借助磁盘构建大型后缀树),压缩以及简化等。
    本文主要考虑字符串所包含的字符集固定并且内存足以支撑整个构建的情况。

    2、后缀树的定义
    假定给定一个长度为m的字符串S(下标从1到m),S的后缀树T为一个有m个叶节点的有根树,其叶节点从1到m编号;除了根节点之外,内个内部节点至少有两个孩子;每条边上都标有S的一个非空子集;从同一个节点引出的任意两条边上标的字符串都不会以相同的字符开始;最后,也是最重要的一点,对任意一个叶节点i,从根节点到i的路径上所有边上标的字符串连接起来,就是S从位置i开始的后缀,也就是说,上述路径恰好拼出了S[i…m],
    Trie树,上述后缀树相当于将S的m个后缀看做m个单词插入到字典树中,同时收缩那些只有一个孩子的内部节点。
    不过,不是所有的字符串都存在这样的后缀树。例如,如果把上述字符串的最后一个字符c去掉,后缀xa就消失了,因为后缀xa恰好是xabxa的前缀,所以按照上述方式构建出来的树就没有m个叶节点了。因此,其根本问题就是有些后缀会是其他后缀的前缀。为了避免这个问题,我们统一在字符串后添加一个S中没有出现过的字符,不妨用S表示。这样,字符串S就一定有对应的后缀树了。
    为了方便表示,我们再定义如下几个概念。
    路径标记:从根节点到某个节点的路径标记,就是该路径上标记的字符串顺次连接得到的字符串,这称作该节点的路径标记。
    字符深度:一个节点的字符深度定义为其路径标记所包含的字符个数。
    深度:一个节点的深度定义为其到根节点路径上经过的边数目。

    后缀树的构建
    在这一节中,我们首先介绍一种易懂但是效率较低的朴素算法,unkonen算法,其原始思想以及直接的暴力实现,然后一步步优化得到最终的线性时间的算法。

    3.1 后缀树的朴素构建算法
    后缀树可以看做压缩过后的Trie树,所以一种直观的朴素算法就是将字符串SmmTrieTrieTrieOm2Om23.2线线线线1995Ukkonen线便unkkoneen1.ukkonenS的m个后缀看做m个单词插入Trie树中,然后按照后缀树的压缩规则——每个内部节点至少有两个孩子,来对Trie树中的内部节点压缩。由于每次插入的时间复杂度与插入的串长度成正比,所以构建Trie树的时间复杂度易知为O(m^2),再加上之后的压缩操作,总的时间复杂度仍为O(m的2次方)。 3.2后缀树的线性时间构造算法 在介绍线性时间构建算法之前,我们有必要证明我们的存储结构(包含节点个数以及边上标记)也至多是线性的。 本书介绍的线性时间构建算法为1995年由Ukkonen提出的。该算法想比较其他线性时间算法而言,主要有能再构建,较容易理解和实现,更节省空间等优势。所以为了便于理解,我们首先一种朴素方式低效的实现unkkoneen算法,然后再进行优化。 1.隐式树的朴素构造,ukkonen的算法过程主要是构建一系列的“隐式树”,其中最后构建的一颗隐式树可以将其转变为我们所要的后缀树。 将S的后缀树中所有边的标记S2SS[1...i]S[1..i]删去,然后删去那些没有标记的边,得到的就是字符串S的隐式树。同时,孩子数目小于2的内部节点也要被删除。类似的,S的前缀S[1...i]的隐式树为字符串S[1..i]的后缀树进行上述操作后得到的树。我们用记号Ti代表S的前缀S[1…i]的隐式树,其中i的取值范围为1到m。
    我们发现,如果一个字符串的某一个后缀是另一个后缀的前缀,那么该字符串的隐式树的叶节点数量就会少其后缀树,这也正是后缀树构建时加上字符$的用意所在。
    unkknen的算法对于每个S的前缀S[1…i]都会构建对应的隐式树Ti,从Ti开始构建,直到Tm构建完成,然后由该隐式树Tm构建我们所需要的后缀树。我们先来看一种该思想的朴素实现方法————一种时间复杂度为O(m的3次方)的算法。
    ukkonen的算法可以分为m个阶段,在第i+1个阶段构造对应的隐式树Ti+1,我们通过隐式树Ti来构建Ti+1。由于后缀树的朴素算法可知,第i+1个阶段构建的前置S[1…i+1]的隐式树需要插入s[1…i+1]的i+1个后缀,所以对于第i+1个阶段,我们进一步将其划分为i+1次扩展。在第i+1个阶段的第j次扩展中,我们将S[1…i+1]的后缀S[j…i+1]插入到隐式树中,由于我们是从Ti构建Ti+1,所以我们当前带插入的后缀S[j…i+1]的前缀S[j…i]已经在树中了,我们只需要根据隐式树定义,看有没有需要将字符S[i+1]插入进去。也就是说,第i+1个阶段将字符S[i+1添加进树Ti来构建Ti+1,而第一阶段只需要将字符S[1]添加进T1即可。整个过程的伪代码如下:
    (先跑步去辽,回来再看)
    伪代码
    function buildimplicitTree()
    Build TreeT1
    for i<-1 to m-1 do
    for j<-1 to i+1 do
    在当前树中找到字符串S[j…i]对应的位置,然后看是否需要添加字符S[i+1]
    End For
    End For
    下面,我们来证明该朴素实现算法的时间复杂度是O(m^3)。首先,外部的两重循环需要的运行时间为O(m的3次方),每次循环执行的任务都需要查找字符串对应的位置,而在树中找到该串所需要的实践与串长度呈线性关系,因此每次查找所需时间复杂度为O(m),故总时间复杂度为O(m的3次方)。似乎比我们最初提到的简单的暴力实现还要慢!不过不用着急,接下来我们就会看到如何利用我们发现的一些规律和技巧来将其优化。

    3.2扩展规则约定
    在开始优化之前,我们对每次扩展规则做个约定:在第i+1阶段的第j次扩展将找到S[j…i]的位置,然后保证S[j…i+1]在树中。
    规则1:串s[j…i]终止于叶节点,也就是说从根节点到该叶节点的路径标记为串S[j…i],此时我们只需要将该叶节点的父边的标记最后加上字符s[i+1]即可。
    规则2:串S[j…i]对应的位置不是叶节点(可能是中间节点,也可能是某条边的内部位置,因为一条边可以代表某个子串),同时,串Sj…i+1]又不在当前树中,那么我们需要将该树进行扩展————如果S[j…i]对应的位置在边内部,那么需要将该边在该位置拆开,然后添加新的节点,这样保证了S[j…i]终止于一个节点;然后新建一个该节点的子节点(新的叶子节点,其间的边标记为S[i+1]。
    规则3:串s[j…i+1]已经在树中找到,那么我们不需要作出任何的修改
    上述规则1和规则3比较直观。由图可知,当插入串“bc”时,路径“b’本来在边的内部,所以创建了一个新的节点,然后加入了新的叶子节点,叶子边对应标记"c"。

    展开全文
  • 后缀树与后缀数组zz

    千次阅读 2007-11-26 18:07:00
    其实后缀数组后缀树的一个非常 精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。可以说,在信息学竞赛中 后缀数组后缀树要更为...

    <script type="text/javascript">function StorePage(){d=document;t=d.selection?(d.selection.type!='None'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():'');void(keyit=window.open('http://www.365key.com/storeit.aspx?t='+escape(d.title)+'&u='+escape(d.location.href)+'&c='+escape(t),'keyit','scrollbars=no,width=475,height=575,left=75,top=20,status=no,resizable=yes'));keyit.focus();}</script> 后缀树:
    后缀树是一种数据结构,它支持有效的字符串匹配和查询。

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

    图中示意了字符串 "I know you know I know "的后缀树。内部节点用圆来表示,叶子用矩形来表示,该例子中有六个叶子,被标号为1到6。 终止字符在图中被省略掉了。

    同理, 若干字符串组成的后缀树, 称为一个扩展的后缀树:n个字符串Sn,其中字符串的长度为mn, 由这些字符串组成一个扩展的后缀树 T ,它是一个包含一个根节点的有向树,该树有mn个叶子,每个叶子都用一个两数字的坐标tuple(k,l)来标识,其中k的范围是从1到n,而l的范围 是从1到mk ,每一个内部节点,除了根节点外,都有两个子节点并且每条边都用一个非空的S中若干单词构成的一个子串来标识。并且出自同一节点的任意两条边的标识的第一 个单词不能相同。对于任意的叶子(i,j),从根节点到该叶子所经历的所有边的标识的串联恰好拼出后缀Si,该后缀从位置j开始,就是说它们拼出了Si [j..mi]。
    在 字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常 精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。可以说,在信息学竞赛中 后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法,以及配合后缀数组的最长公共前缀数组的构造方法,最后结合一些例 子谈谈后缀数组的应用。


    后缀数组:

    首先明确一些必要的定义:

    字符集 一个字符集∑是一个建立了全序关系的集合,也就是说,∑中的任意两个不同的元素α和β都可以比较大小,要么α<β,要么β<α(也就是α>β)。字符集∑中的元素称为字符。
    字符串 一个字符串S是将n个字符顺次排列形成的数组,n称为S的长度,表示为len(S)。S的第i个字符表示为S[i]。
    子串 字符串S的子串S[i..j],i≤j,表示S串中从i到j这一段,也就是顺次排列S[i],S[i+1],...,S[j]形成的字符串。
    后缀 后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i),也就是Suffix(S,i)=S[i..len(S)]。

    关 于字符串的大小比较,是指通常所说的“字典顺序”比较,也就是对于两个字符串u、v,令i从1开始顺次比较u[i]和v[i],如果相等则令i加1,否则 若u[i]<v[i]则认为u<v,u[i]>v[i]则认为u>v(也就是v<u),比较结束。如果i>len (u)或者i>len(v)仍未比较出结果,那么若len(u)<len(v)则认为u<v,若len(u)=len(v)则认为u= v,若len(u)>len(v)则u>v。
    从字符串的大小比较的定义来看,S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等,因为u=v的必要条件len(u)=len(v)在这里不可能满足。

    下 面我们约定一个字符集∑和一个字符串S,设len(S)=n,且S[n]='$',也就是说S以一个特殊字符'$'结尾,并且'$'小于∑中的任何一个字 符。除了S[n]之外,S中的其他字符都属于∑。对于约定的字符串S,从位置i开头的后缀直接写成Suffix(i),省去参数S。

    后 缀数组 后缀数组SA是一个一维数组,它保存1..n的某个排列SA[1],SA[2],...SA[n],并且保证 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头 位置顺次放入SA中。
    名次数组 名次数组Rank=SA-1,也就是说若SA[i]=j,则Rank[j]=i,不难看出Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。


    构造方法
    如何构造后缀数组呢?最直接最简单的方法当然是把S的后缀都看作一些普通的字符串,按照一般字符串排序的方法对它们从小到大进行排序。
    不难看出,这种做法是很笨拙的,因为它没有利用到各个后缀之间的有机联系,所以它的效率不可能很高。即使采用字符串排序中比较高效的Multi-key Quick Sort,最坏情况的时间复杂度仍然是O(n2)的,不能满足我们的需要。
    下面介绍倍增算法(Doubling Algorithm),它正是充分利用了各个后缀之间的联系,将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。

    对一个字符串u,我们定义u的k-前缀

    定义k-前缀比较关系<k、=k和≤k:
    设两个字符串u和v,
    u<kv 当且仅当 uk<vk
    u=kv 当且仅当 uk=vk
    u≤kv 当且仅当 uk≤vk

    直观地看这些加了一个下标k的比较符号的意义就是对两个字符串的前k个字符进行字典序比较,特别的一点就是在作大于和小于的比较时如果某个字符串的长度不到k也没有关系,只要能够在k个字符比较结束之前得到第一个字符串大于或者小于第二个字符串就可以了。
    根据前缀比较符的性质我们可以得到以下的非常重要的性质:
    性质1.1 对k≥n,Suffix(i)<kSuffix(j) 等价于 Suffix(i)<Suffix(j)。
    性质1.2 Suffix(i)=2kSuffix(j)等价于
    Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
    性质1.3 Suffix(i)<2kSuffix(j) 等价于
    Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
    这 里有一个问题,当i+k>n或者j+k>n的时候Suffix(i+k)或Suffix(j+k)是无明确定义的表达式,但实际上不需要考虑 这个问题,因为此时Suffix(i)或者Suffix(j)的长度不超过k,也就是说它们的k-前缀以'$'结尾,于是k-前缀比较的结果不可能相等, 也就是说前k个字符已经能够比出大小,后面的表达式自然可以忽略,这也就看出我们规定S以'$'结尾的特殊用处了。

    定义k-后缀数组 SAk保存1..n的某个排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是说对所有的后缀在k-前缀比较关系下从小到大排序,并且把排序后的后缀的开头位置顺次放 入数组SAk中。
    定义k-名次数组Rankk,Rankk[i]代表Suffix(i)在k-前缀关系下从小到大的“名次”,也就是1加上满足Suffix(j)<kSuffix(i)的j的个数。通过SAk很容易在O(n)的时间内求出Rankk。
    假 设我们已经求出了SAk和Rankk,那么我们可以很方便地求出SA2k和Rank2k,因为根据性质1.2和1.3,2k-前缀比较关系可以由常数个k -前缀比较关系组合起来等价地表达,而Rankk数组实际上给出了在常数时间内进行<k和=k比较的方法,即:
    Suffix(i)<kSuffix(j) 当且仅当 Rankk[i]<Rankk[j]
    Suffix(i)=kSuffix(j) 当且仅当 Rankk[i]=Rankk[j]
    因 此,比较Suffix(i)和Suffix(j)在k-前缀比较关系下的大小可以在常数时间内完成,于是对所有的后缀在≤k关系下进行排序也就和一般的排 序没有什么区别了,它实际上就相当于每个Suffix(i)有一个主关键字Rankk[i]和一个次关键字Rankk[i+k]。如果采用快速排序之类O (nlogn)的排序,那么从SAk和Rankk构造出SA2k的复杂度就是O(nlogn)。更聪明的方法是采用基数排序,复杂度为O(n)。
    求出SA2k之后就可以在O(n)的时间内根据SA2k构造出Rank2k。因此,从SAk和Rankk推出SA2k和Rank2k可以在O(n)时间内完成。
    下 面只有一个问题需要解决:如何构造出SA1和Rank1。这个问题非常简单:因为<1,=1和≤1这些运算符实际上就是对字符串的第一个字符进行比 较,所以只要把每个后缀按照它的第一个字符进行排序就可以求出SA1,不妨就采用快速排序,复杂度为O(nlogn)。
    于是,可以在O(nlogn)的时间内求出SA1和Rank1。
    求出了SA1和Rank1,我们可以在O(n)的时间内求出SA2和Rank2,同样,我们可以再用O(n)的时间求出SA4和Rank4,这样,我们依次求出:
    SA2和Rank2,SA4和Rank4,SA8和Rank8,……直到SAm和Rankm,其中m=2k且m≥n。而根据性质1.1,SAm和SA是等价的。这样一共需要进行logn次O(n)的过程,因此
    可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。

    最长公共前缀
    现 在一个字符串S的后缀数组SA可以在O(nlogn)的时间内计算出来。利用SA我们已经可以做很多事情,比如在O(mlogn)的时间内进行模式匹配, 其中m,n分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力,我们还需要计算一个辅助的工具——最长公共前缀(Longest Common Prefix)。
    对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv},也就是从头开始顺次比较u和v的对应字符,对应字符持续相等的最大位置,称为这两个字符串的最长公共前缀。
    对正整数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(i,j)显然是很低效的,时间复杂度为O(n),所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。
    经过仔细分析,我们发现LCP函数有一个非常好的性质:
    设i<j,则LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} (LCP Theorem)

    要证明LCP Theorem,首先证明LCP Lemma:
    对任意1≤i<j<k≤n,LCP(i,k)=min{LCP(i,j),LCP(j,k)}
    证明:设p=min{LCP(i,j),LCP(j,k)},则有LCP(i,j)≥p,LCP(j,k)≥p。
    设Suffix(SA[i])=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
    由u=LCP(i,j)v得u=pv;同理v=pw。
    于是Suffix(SA[i])=pSuffix(SA[k]),即LCP(i,k)≥p。 (1)

    又设LCP(i,k)=q>p,则
    u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
    而min{LCP(i,j),LCP(j,k)}=p说明u[p+1]≠v[p+1]或v[p+1]≠w[q+1],
    设u[p+1]=x,v[p+1]=y,w[p+1]=z,显然有x≤y≤z,又由p<q得p+1≤q,应该有x=z,也就是x=y=z,这与u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
    于是,q>p不成立,即LCP(i,k)≤p。 (2)
    综合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)},LCP Lemma得证。

    于是LCP Theorem可以证明如下:
    当j-i=1和j-i=2时,显然成立。
    设j-i=m时LCP Theorem成立,当j-i=m+1时,
    由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)},
    因j-(i+1)≤m,LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j},故当j-i=m+1时,仍有
    LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
    根据数学归纳法,LCP Theorem成立。

    根据LCP Theorem得出必然的一个推论:
    LCP Corollary 对i≤j<k,LCP(j,k)≥LCP(i,k)。

    定义一维数组height,令height[i]=LCP(i-1,i),1<i≤n,并设height[1]=0。
    由LCP Theorem,LCP(i,j)=min{height[k]|i+1≤k≤j},也就是说,计算LCP(i,j)等同于询问一维数组height中下 标在i+1到j范围内的所有元素的最小值。如果height数组是固定的,这就是非常经典的RMQ(Range Minimum Query)问题。
    RMQ问题可以用线段树或静态排序树在O(nlogn)时间内进行预处理,之后每次询问花费时间O(logn),更好的方法是RMQ标准算法,可以在O(n)时间内进行预处理,每次询问可以在常数时间内完成。
    对于一个固定的字符串S,其height数组显然是固定的,只要我们能高效地求出height数组,那么运用RMQ方法进行预处理之后,每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题——如何尽量高效地算出height数组。
    根据计算后缀数组的经验,我们不应该把n个后缀看作互不相关的普通字符串,而应该尽量利用它们之间的联系,下面证明一个非常有用的性质:
    为了描述方便,设h[i]=height[Rank[i]],即height[i]=h[SA[i]]。h数组满足一个性质:
    性质3 对于i>1且Rank[i]>1,一定有h[i]≥h[i-1]-1。
    为了证明性质3,我们有必要明确两个事实:

    设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。
    看 起来很神奇,但其实很自然:lcp(Suffix(i),Suffix(j))>1说明Suffix(i)和Suffix(j)的第一个字符是相同 的,设它为α,则Suffix(i)相当于α后连接Suffix(i+1),Suffix(j)相当于α后连接Suffix(j+1)。比较Suffix (i)和Suffix(j)时,第一个字符α是一定相等的,于是后面就等价于比较Suffix(i)和Suffix(j),因此Fact 1成立。Fact 2可类似证明。

    于是可以证明性质3:
    当h[i-1]≤1时,结论显然成立,因h[i]≥0≥h[i-1]-1。
    当h[i-1]>1时,也即height[Rank[i-1]]>1,可见Rank[i-1]>1,因height[1]=0。
    令j=i-1,k=SA[Rank[j]-1]。显然有Suffix(k)<Suffix(j)。
    根据h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j):
    由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
    由Fact 1知Rank[k+1]<Rank[i],也就是Rank[k+1]≤Rank[i]-1。
    于是根据LCP Corollary,有
    LCP(Rank[i]-1,Rank[i])≥LCP(Rank[k+1],Rank[i])
    =lcp(Suffix(k+1),Suffix(i))
    =h[i-1]-1
    由于h[i]=height[Rank[i]]=LCP(Rank[i]-1,Rank[i]),最终得到 h[i]≥h[i-1]-1。

    根据性质3,可以令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。

    设SA[1]=p,那么不难看出总的字符比较次数不超过

    也就是说,整个算法的复杂度为O(n)。
    求出了h数组,根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组,于是
    可以在O(n)时间内求出height数组。

    结合RMQ方法,在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。
    因为lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j]),所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。 

    WiKi Answer:
    suffix tree
    Suffix tree for the string BANANA padded with $. The six paths from the root to a leaf (shown as boxes) correspond to the six suffixes A$, NA$, ANA$, NANA$, ANANA$ and BANANA$. The numbers in the boxes give the start position of the corresponding suffix. Suffix links drawn dashed.

    Suffix tree for the string BANANA padded with $. The six paths from the root to a leaf (shown as boxes) correspond to the six suffixes A$, NA$, ANA$, NANA$, ANANA$ and BANANA$. The numbers in the boxes give the start position of the corresponding suffix. Suffix links drawn dashed.

    In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a certain data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.

    The suffix tree for a string S is a tree whose edges are labeled with strings, and such that each suffix of S corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree for the suffixes of S.

    Constructing such a tree for the string S takes time and space linear in the length of S. Once constructed, several operations can be performed quickly, for instance locating a substring in S, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provided one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.

    History

    The concept was first introduced as a position tree by Weiner in 1973[1] in a paper which Donald Knuth subsequently characterized as "Algorithm of the Year 1973". The construction was greatly simplified by McCreight in 1976 [2] , and also by Ukkonen in 1995[3][4]. Ukkonen provided the first linear-time online-construction of suffix trees, now known as Ukkonen's algorithm.

    Definition

    The suffix tree for the string S of length n is defined as a tree such that ([5] page 90):

    • the paths from the root to the leaves have a one-to-one relationship with the suffixes of S,
    • edges spell non-empty strings,
    • and all internal nodes (except perhaps the root) have at least two children.

    Since such a tree does not exist for all strings, S is padded with a terminal symbol not seen in the string (usually denoted $). This ensures that no suffix is a prefix of another, and that there will be n leaf nodes, one for each of the n suffixes of S. Since all internal non-root nodes are branching, there can be at most n - 1 such nodes, and n + (n - 1) + 1 = 2n nodes in total.

    Suffix links are a key feature for linear-time construction of the tree. In a complete suffix tree, all internal non-root nodes have a suffix link to another internal node. If the path from the root to a node spells the string χα, where χ is a single character and α is a string (possibly empty), it has a suffix link to the internal node representing α. See for example the suffix link from the node for ANA to the node for NA in the figure above. Suffix links are also used in some algorithms running on the tree.

    Functionality

    A suffix tree for a string S of length n can be built in Θ(n) time, if the alphabet is constant or integer [6]. Otherwise, the construction time depends on the implementation. The costs below are given under the assumption that the alphabet is constant. If it is not, the cost depends on the implementation (see below).

    Assume that a suffix tree has been built for the string S of length n, or that a generalised suffix tree has been built for the set of strings D = {S1,S2,...,SK} of total length n = | n1 | + | n2 | + ... + | nK | . You can:

    • Search for strings:
      • Check if a string P of length m is a substring in O(m) time ([5] page 92).
      • Find the first occurrence of the patterns P1,...,Pq of total length m as substrings in O(m) time, when the suffix tree is built using Ukkonen's algorithm.
      • Find all z occurrences of the patterns P1,...,Pq of total length m as substrings in O(m + z) time ([5] page 123).
      • Search for a regular expression P in time expected sublinear on n ([7]).
      • Find for each suffix of a pattern P, the length of the longest match between a prefix of P[i...m] and a substring in D in Θ(m) time ([5] page 132). This is termed the matching statistics for P.
    • Find properties of the strings:
      • Find the longest common substrings of the string Si and Sj in Θ(ni + nj) time ([5] page 125).
      • Find all maximal pairs, maximal repeats or supermaximal repeats in Θ(n + z) time ([5] page 144).
      • Find the Lempel-Ziv decomposition in Θ(n) time ([5] page 166).
      • Find the longest repeated substrings in Θ(n) time.
      • Find the most frequently occurring substrings of a minimum length in Θ(n) time.
      • Find the shortest strings from Σ that do not occur in D, in O(n + z) time, if there are z such strings.
      • Find the shortest substrings occurring only once in Θ(n) time.
      • Find, for each i, the shortest substrings of Si not occurring elsewhere in D in Θ(n) time.

    The suffix tree can be prepared for constant time lowest common ancestor retrieval between nodes in Θ(n) time ([5] chapter 8). You can then also:

    • Find the longest common prefix between the suffixes Si[p..ni] and Sj[q..nj] in Θ(1) ([5] page 196).
    • Search for a pattern P of length m with at most k mismatches in O(kn + z) time, where z is the number of hits ([5] page 200).
    • Find all z maximal palindromes in Θ(n)([5] page 198), or Θ(gn) time if gaps of length g are allowed, or Θ(kn) if k mismatches are allowed ([5] page 201).
    • Find all z tandem repeats in O(nlogn + z), and k-mismatch tandem repeats in O(knlog(n / k) + z) ([5] page 204).
    • Find the longest substrings common to at least k strings in D for k = 2..K in Θ(n) time ([5] page 205).

    Uses

    Suffix trees are often used in bioinformatics applications, where they are used for searching for patterns in DNA or protein sequences, which can be viewed as long strings of characters. The ability to search efficiently with mismatches might be the suffix tree's greatest strength. It is also used in data compression, where on the one hand it is used to find repeated data and on the other hand it can be used for the sorting stage of the Burrows-Wheeler transform. Variants of the LZW compression schemes use it (LZSS). A suffix tree is also used in something called suffix tree clustering which is a data clustering algorithm used in some search engines.

    Implementation

    If each node and edge can be represented in Θ(1) space, the entire tree can be represented in Θ(n) space. The total length of the edges in the tree is O(n2), but each edge can be stored as the position and length of a substring of S, giving a total space usage of Θ(n) computer words. The worst-case space usage of a suffix tree is seen with a fibonacci string, giving the full 2n nodes.

    An important choice when making a suffix tree implementation is the parent-child relationships between nodes. The most common is using linked lists called sibling lists. Each node has pointer to its first child, and to the next node in the child list it is a part of. Hash maps, sorted/unsorted arrays (with array doubling), and balanced search trees may also be used, giving different running time properties. We are interested in:

    • The cost of finding the child on a given character.
    • The cost of inserting a child.
    • The cost of enlisting all children of a node (divided by the number of children in the table below).

    Let σ be the size of the alphabet. Then you have the following costs:

      Lookup Insertion Traversal
    Sibling lists / unsorted arrays O(σ) Θ(1) Θ(1)
    Hash maps Θ(1) Θ(1) O(σ)
    Balanced search tree O(logσ) O(logσ) O(1)
    Sorted arrays O(logσ) O(σ) O(1)
    Hash maps + sibling lists O(1) O(1) O(1)

    Note that the insertion cost is amortised, and that the costs for hashing are given perfect hashing.

    The large amount of information in each edge and node makes the suffix tree very expensive, consuming about ten to twenty times the memory size of the source text in good implementations. The suffix array reduces this requirement to a factor of four, and researchers have continued to find smaller indexing structures.

    See also

    References

    1. ^ P. Weiner (1973). "Linear pattern matching algorithm". 14th Annual IEEE Symposium on Switching and Automata Theory: 1-11. 
    2. ^ Edward M. McCreight (1976). "A Space-Economical Suffix Tree Construction Algorithm". Journal of the ACM 23 (2): 262--272. 
    3. ^ E. Ukkonen (1995). "On-line construction of suffix trees". Algorithmica 14 (3): 249--260. 
    4. ^ R. Giegerich and S. Kurtz (1997). "From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction". Algorithmica 19 (3): 331--353. 
    5. ^ a b c d e f g h i j k l m n Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. 
    6. ^ Martin Farach (1997). "Optimal suffix tree construction with large alphabets". Foundations of Computer Science, 38th Annual Symposium on: 137--143. 
    7. ^ Ricardo A. Baeza-Yates and Gaston H. Gonnet (1996). "Fast text searching for regular expressions or automaton searching on tries". Journal of the ACM 43: 915--936. DOI:10.1145/235809.235810. ISSN 0004-5411. 

    External links

    ======================
    看两个例子先

    因 suffix link 难于在字符图内表示,故略之。
     
    apple: |--apple$--[0]
           |--e$--[4]
           |--le$--[3]
           |--p--|--le$--[2]
                 |--ple$--[1]
     
    banana: |--a--|--$--[5]
            |     |--na--|--$--[3]
            |     |      |--na$--[1]
            |--banana$--[0]
            |--na--|--$--[4]
            |      |--na$--[2]
     
    后缀树有什么用
     
    同样是上面那个链接,在 Functionality 一栏,可以看到详细的描述。因为当中的条目,是本系列篇什的行动指南,故录之于此。

    A suffix tree for a string S of length n can be built in Θ(n) time, if the alphabet is constant or integer. Otherwise, the construction time depends on the implementation. The costs below are given under the assumption that the alphabet is constant. If it is not, the cost depends on the implementation (see below).
     
    若字符集恒定或为整数,则一个长为 n 的字符串 S,其后缀树可于 Θ(n) 的时间内得以构建。否则,构造时间依实现而定。如下给出的开销数据即基于字符集为恒定的假设。若字符集不为恒定,则开销依实现而定。(偶发现【翻译】是一件及其痛苦和费时的事,决意以后不再翻译!)
     
    Assume that a suffix tree has been built for the string S of length n, or that a generalised suffix tree has been built for the set of strings D = {S1,S2,...,SK} of total length n = | n1 | + | n2 | + ... + | nK | . You can:

    • Search for strings:
      • Check if a string P of length m is a substring in O(m) time.
      • Find all z occurrences of the patterns P1,...,Pq of total length m as substrings in O(m + z) time.
      • Search for a regular expression P in time expected sublinear on n.
      • Find for each suffix of a pattern P, the length of the longest match between a prefix of P[i...m] and a substring in D in Θ(m) time. This is termed the matching statistics for P.
    • Find properties of the strings:
      • Find the longest common substrings of the string Si and Sj in Θ(ni + nj) time.
      • Find all maximal pairs, maximal repeats or supermaximal repeats in Θ(n + z) time.
      • Find the Lempel-Ziv decomposition in Θ(n) time.
      • Find the longest repeated substrings in Θ(n) time.
      • Find the most frequently occurring substrings of a minimum length in Θ(n) time.
      • Find the shortest strings from Σ that do not occur in D, in O(n + z) time, if there are z such strings.
      • Find the shortest substrings occurring only once in Θ(n) time.
      • Find, for each i, the shortest substrings of Si not occurring elsewhere in D in Θ(n) time.

    The suffix tree can be prepared for constant time lowest common ancestor retrieval between nodes in Θ(n) time. You can then also:

    • Find the longest common prefix between the suffixes Si[p..ni] and Sj[q..nj in Θ(1).
    • Search for a pattern P of length m with at most k mismatches in O(kn + z) time, where z is the number of hits.
    • Find all z maximal palindromes in Θ(n), or Θ(gn) time if gaps of length g are allowed, or Θ(kn) if k mismatches are allowed.
    • Find all z tandem repeats in O(nlogn + z), and k-mismatch tandem repeats in O(knlog(n / k) + z).
    • Find the longest substrings common to at least k strings in D for k = 2..K in Θ(n) time.

    ==================

    Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1857530

     
    展开全文
  • 字符串:KMP Eentend-Kmp 自动机 trie图 trie树 后缀树 后缀数组  2009-09-25 00:00:40| 分类: 算法acm|字号 订阅 涉及到字符串的问题,无外乎这样一些算法和数据结构:自动机 KMP算法 ...
  • 字符串:KMP Eentend-Kmp 自动机 trie图 trie树 后缀树 后缀数组 - 星星的日志 - 网易博客字符串:KMP Eentend-Kmp 自动机 trie图 trie树 后缀树 后缀数组 2009-09-25 00:00:40| 分类: 算法acm | 标签: |...
  • 后缀数组学习练习(入门向) Zbq 算法概述: 首先后缀数组SA是后缀数组后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的...
  • 后缀数组后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能且时间复杂度也并不逊色,而且它比后缀树所占用的内存空间小很多。可以说,在信息学竞赛中后缀数组后缀树要更为实用。...
  • 解法一:后缀数组 显然将原数组差分后答案就是所有不相交不相邻重复子串个数+n*(n-1)/2。 答案=重复子串个数-相邻或相交重复子串个数。 前者单调栈直接求解,注意细节,重点在后者。 由于是有关相交的计数问题,...
  • 后缀数组真神奇。   【后缀】 对于一个字符串,定义suffix(i)为以i起点至结尾的子串。例如ababc,suffix(3)=bc   【后缀树后缀树容易理解,就是把一个字符串的所有后缀串插入到一个字典树上(字典树不再...
  • 我们可以通过后缀数组,显然从x开始的后缀中最短的就是前后两个height中最大的一个+1,因为最大的那个使能匹配的最多,那么再加一位显然就不能匹配了 那么这一段的值都可以更新为这个长度,那么用线段维护就好...
  • 给你一个1e5的字符串,1e5组询问,求\([l_1,r_1]\)的所有子串\([l_2,r_2]\)的lcp 思路: 首先可以发现答案是具有单调性的,我们考虑二分答案,二分的范围显然为\([0,min(r_2-l_2+1,r_1-l_1+1)]\) 对于二分到的字符...
  • LCS与后缀数组

    2009-03-02 23:56:33
    后缀树的方法 ,看了编程珠玑后觉得后缀树组更简洁高效 ,故重新实现下 找出单个字符串最长的重复子串以及最长的出现m次的子串。   import java.util.ArrayList; import java.util.Collections; /...
  • 对于询问,把两条链拆成一些重链的片段,然后两个指针枚举每个片段,用后缀数组找片段片段的 LCP ,直到一次 LCP 的长度比两个片段的长度都小,说明两条链的 LCP 截止于此。 把重链放到序列上其实...
  • 思路:后缀数组sa[i]数组表示排名第i的后缀第一次出现的下标,求第k次出现的下标只需要在某个区间中求sa数组中的第k大即可(主席求第k大),确定区间时利用后缀数组中的lcp确定子串具有相同前缀的后缀第一次出现...
  • 思路:首先询问许多子串的这种问题应该联想到后缀数组,然后我们发现对于后缀数组中的排序(sa[i]表示下标为i的后缀的排名,rk[i]表示排名为i的后缀的下标),每个后缀串子串的最长公共前缀为该子串的串是连续的,...
  • 二分答案 t,在后缀数组上找到 [c,d] LCP 大于等于 t 的区间 [l,r]。 相当于询问 [l,r] 中是否存在 [a,b − t + 1] 里的数字 主席#include #include #include using namespace std;inline char nc(){ static ...
  • 大意: 给定串s,q个询问(l,r,k), 求子串s[l,r]的第kk次出现位置. 这是一篇很好的题解: ... 加点个人: 我对上面的题解更为详细...后缀数组处理出来的heigth[] 数组 有个这样的性质: 对于排名 a 的后缀字符串 排...
  • 题目描述: CJB来到HZ王国旅游。HZ王国给CJB留下了深刻的印象,特别是HZ王国的道路系统。HZ王国有N个城市,编号从1到N。其中,城市1为HZ王国的首都。...如果城市A连接的道路数量等于城市B连接的道路数...
  • 注意后缀数组两个位置间的height取minmin\min建虚等价,进一步,两个字符串的lcplcplcp是后缀数组上height取minmin\min,我们按照在后缀数组上相邻的位置排序,建一个新heightheightheight数组,就相当原来的...
  • Problem求字符串 S 中严格出现 k 次的子串个数k≥1k\ge 1|S|≤105|S|\le 10^5∑|S|≤2...后缀数组 + 线段 解法:利用后缀数组处理出 height[] 数组,显然 height[i] 表示 sa[i] sa[i-1] 的最长公共前缀(LCP) 。利
  • 在这个问题中,给定一个字符串S,一个整数K,定义S的子串T=S(i, j)是关于第K位的识别子串,满足以下两个条件: 1、i≤K≤j。 2、子串T只在S中出现过一次。 例如,S=”banana”,K=5,则关于第K位的识别子串有”...
  • 根据一个简单的定理,这个在求height数组的时候貌似有些资料提到过,lcp(i,j)=min(h[k] | i),即排名第i和第j的两个后缀,他们的lcp为二者的左开右闭区间的height[Rank[]]数组的最小值。有N个这样的子串,我们只...
  • 添加链接描述 题解: 一般这种和子串有关的都能扯到后缀数组,由于要找一个...所以就可以先求出后缀数组 sa 和 lcp 的 height 数组,接着对于每次查询先二分该子串所在排名的满足条件的最左区间最右区间,可以用ST...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 278
精华内容 111
关键字:

后缀树与后缀数组