下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 后缀数组

后缀数组.pdf

后缀数组

wangxiang5252
2013-11-21 0人阅读 举报 0 0 暂无简介

简介:本文档为《后缀数组pdf》,可适用于IT/计算机领域

IOI国家集训队论文许智磊第页共页后缀数组安徽省芜湖市第一中学许智磊【摘要】本文介绍后缀数组的基本概念、方法以及应用。首先介绍O(nlogn)复杂度构造后缀数组的倍增算法接着介绍了配合后缀数组的最长公共前缀LCP(LongestCommonPrefix)的计算方法并给出一个线性时间内计算height数组(记录跨度为的LCP值的数组)的算法。为了让读者对如何运用后缀数组有一个感性认识还介绍了两个应用后缀数组的例子:多模式串的模式匹配(给出每次匹配O(mlogn)时间复杂度的算法)以及求最长回文子串(给出O(nlogn)时间复杂度的算法)。最后对后缀数组和后缀树作了一番比较。【关键字】字符串后缀k前缀比较关系后缀数组名次数组后缀树倍增算法基数排序最长公共前缀RMQ问题模式匹配回文串最长回文子串【正文】在字符串处理当中后缀树和后缀数组都是非常有力的工具其中后缀树大家了解得比较多关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品它比后缀树容易编程实现能够实现后缀树的很多功能而时间复杂度也不太逊色并且它比后缀树所占用的空间小很多。可以说在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法以及配合后缀数组的最长公共前缀数组的构造方法最后结合一些例子谈谈后缀数组的应用。IOI国家集训队论文许智磊第页共页基本概念首先明确一些必要的定义:字符集一个字符集Σ是一个建立了全序关系的集合也就是说Σ中的任意两个不同的元素α和β都可以比较大小要么α<β要么β<α(也就是α>β)。字符集Σ中的元素称为字符。字符串一个字符串S是将n个字符顺次排列形成的数组n称为S的长度表示为len(S)。S的第i个字符表示为Si。子串字符串S的子串Siji≤j表示S串中从i到j这一段也就是顺次排列Si,Si,,Sj形成的字符串。后缀后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)也就是Suffix(S,i)=Silen(S)。关于字符串的大小比较是指通常所说的“字典顺序”比较也就是对于两个字符串u、v令i从开始顺次比较ui和vi如果ui=vi则令i加否则若ui<vi则认为u<vui>vi则认为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且Sn='$'也就是说S以一个特殊字符'$'结尾并且'$'小于Σ中的任何一个字符。除了Sn之外S中的其他字符都属于Σ。对于约定的字符串S从位置i开头的后缀直接写成Suffix(i)省去参数S。后缀数组后缀数组SA是一个一维数组它保存n的某个排列SA,SA,SAn并且保证Suffix(SAi)<Suffix(SAi),≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。名次数组名次数组Rank=SA也就是说若SAi=j则Rankj=i不难看出Ranki保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。构造方法如何构造后缀数组呢?最直接最简单的方法当然是把S的后缀都看作一些普通的字符串按照一般字符串排序的方法对它们从小到大进行排序。不难看出这种做法是很笨拙的因为它没有利用到各个后缀之间的有机联系所以它的效率不可能很高。即使采用字符串排序中比较高效的MultikeyQuickSort最坏情况的时间复杂度仍然是O(n)的不能满足我们的需要。IOI国家集训队论文许智磊第页共页下面介绍倍增算法(DoublingAlgorithm)它正是充分利用了各个后缀之间的联系将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。对一个字符串u我们定义u的k前缀îíì<³=kulenukulenkuuk)(,)(,定义k前缀比较关系<k、=k和≤k:设两个字符串u和vu<kv当且仅当uk<vku=kv当且仅当uk=vku≤kv当且仅当uk≤vk直观地看这些加了一个下标k的比较符号的意义就是对两个字符串的前k个字符进行字典序比较特别的一点就是在作大于和小于的比较时如果某个字符串的长度不到k也没有关系只要能够在k个字符比较结束之前得到第一个字符串大于或者小于第二个字符串就可以了。根据前缀比较符的性质我们可以得到以下的非常重要的性质:性质对k≥nSuffix(i)<kSuffix(j)等价于Suffix(i)<Suffix(j)。性质Suffix(i)=kSuffix(j)等价于Suffix(i)=kSuffix(j)且Suffix(ik)=kSuffix(jk)。性质Suffix(i)<kSuffix(j)等价于Suffix(i)<kS(j)或(Suffix(i)=kSuffix(j)且Suffix(ik)<kSuffix(jk))。这里有一个问题当ik>n或者jk>n的时候Suffix(ik)或Suffix(jk)是无明确定义的表达式但实际上不需要考虑这个问题因为此时Suffix(i)或者Suffix(j)的长度不超过k也就是说它们的k前缀以'$'结尾于是k前缀比较的结果不可能相等也就是说前k个字符已经能够比出大小后面的表达式自然可以忽略这也就看出我们规定S以'$'结尾的特殊用处了。定义k后缀数组SAk保存n的某个排列SAk,SAk,…SAkn使得Suffix(SAki)≤kSuffix(SAki),≤i<n。也就是说对所有的后缀在k前缀比较关系下从小到大排序并且把排序后的后缀的开头位置顺次放入数组SAk中。定义k名次数组RankkRankki代表Suffix(i)在k前缀关系下从小到大的“名次”也就是加上满足Suffix(j)<kSuffix(i)的j的个数。通过SAk很容易在O(n)的时间内求出Rankk。假设我们已经求出了SAk和Rankk那么我们可以很方便地求出SAk和Rankk因为根据性质和k前缀比较关系可以由常数个k前缀比较关系组合起来等价地表达而Rankk数组实际上给出了在常数时间内进行<k和=k比较的方法即:Suffix(i)<kSuffix(j)当且仅当Rankki<RankkjSuffix(i)=kSuffix(j)当且仅当Rankki=Rankkj因此比较Suffix(i)和Suffix(j)在k前缀比较关系下的大小可以在常数时间内完成于是对所有的后缀在≤k关系下进行排序也就和一般的排序没有什么区别了它实际上就相当于每个Suffix(i)有一个主关键字Rankki和一个次关键字Rankkik。如果采用快速排序之类O(nlogn)的排序那么从SAk和Rankk构造IOI国家集训队论文许智磊第页共页出SAk的复杂度就是O(nlogn)。更聪明的方法是采用基数排序复杂度为O(n)。求出SAk之后就可以在O(n)的时间内根据SAk构造出Rankk。因此从SAk和Rankk推出SAk和Rankk可以在O(n)时间内完成。下面只有一个问题需要解决:如何构造出SA和Rank。这个问题非常简单:因为<=和≤这些运算符实际上就是对字符串的第一个字符进行比较所以只要把每个后缀按照它的第一个字符进行排序就可以求出SA不妨就采用快速排序复杂度为O(nlogn)。于是可以在O(nlogn)的时间内求出SA和Rank。求出了SA和Rank我们可以在O(n)的时间内求出SA和Rank同样我们可以再用O(n)的时间求出SA和Rank这样我们依次求出:SA和RankSA和RankSA和Rank……直到SAm和Rankm其中m=k且m≥n。而根据性质SAm和SA是等价的。这样一共需要进行logn次O(n)的过程因此可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。最长公共前缀现在一个字符串S的后缀数组SA可以在O(nlogn)的时间内计算出来。利用SA我们已经可以做很多事情比如在O(mlogn)的时间内进行模式匹配其中m,n分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力我们还需要计算一个辅助的工具最长公共前缀(LongestCommonPrefix)。对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}也就是从头开始顺次比较u和v的对应字符对应字符持续相等的最大位置称为这两个字符串的最长公共前缀。对正整数i,j定义LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj)其中i,j均为至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。关于LCP有两个显而易见的性质:性质LCP(i,j)=LCP(j,i)性质LCP(i,i)=len(Suffix(SAi))=nSAi这两个性质的用处在于我们计算LCP(i,j)时只需要考虑i<j的情况因为i>j时可交换i,ji=j时可以直接输出结果nSAi。直接根据定义用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的时间复杂度为O(n)所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。经过仔细分析我们发现LCP函数有一个非常好的性质:设i<j则LCP(i,j)=min{LCP(k,k)|i≤k≤j}(LCPTheorem)要证明LCPTheorem首先证明LCPLemma:对任意≤i<j<k≤nLCP(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。IOI国家集训队论文许智磊第页共页设Suffix(SAi)=u,Suffix(SAj)=v,Suffix(SAk)=w。由u=LCP(i,j)v得u=pv同理v=pw。于是Suffix(SAi)=pSuffix(SAk)即LCP(i,k)≥p。()又设LCP(i,k)=q>p则u=w,u=w,uq=wq。而min{LCP(i,j),LCP(j,k)}=p说明up≠vp或vp≠wq设up=x,vp=y,wp=z显然有x≤y≤z又由p<q得p≤q应该有x=z也就是x=y=z这与up≠vp或vp≠wq矛盾。于是q>p不成立即LCP(i,k)≤p。()综合(),()知LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}LCPLemma得证。于是LCPTheorem可以证明如下:当ji=和ji=时显然成立。设ji=m时LCPTheorem成立当ji=m时由LCPLemma知LCP(i,j)=min{LCP(i,i),LCP(i,j)}因j(i)≤mLCP(i,j)=min{LCP(k,k)|i≤k≤j}故当ji=m时仍有LCP(i,j)=min{LCP(i,i),min{LCP(k,k)|i≤k≤j}}=min{LCP(k,k}|i≤k≤j)根据数学归纳法LCPTheorem成立。根据LCPTheorem得出必然的一个推论:LCPCorollary对i≤j<kLCP(j,k)≥LCP(i,k)。定义一维数组height令heighti=LCP(i,i)<i≤n并设height=。由LCPTheoremLCP(i,j)=min{heightk|i≤k≤j}也就是说计算LCP(i,j)等同于询问一维数组height中下标在i到j范围内的所有元素的最小值。如果height数组是固定的这就是非常经典的RMQ(RangeMinimumQuery)问题。RMQ问题可以用线段树或静态排序树在O(nlogn)时间内进行预处理之后每次询问花费时间O(logn)更好的方法是RMQ标准算法可以在O(n)时间内进行预处理每次询问可以在常数时间内完成。对于一个固定的字符串S其height数组显然是固定的只要我们能高效地求出height数组那么运用RMQ方法进行预处理之后每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题如何尽量高效地算出height数组。根据计算后缀数组的经验我们不应该把n个后缀看作互不相关的普通字符串而应该尽量利用它们之间的联系下面证明一个非常有用的性质:为了描述方便设hi=heightRanki即heighti=hSAi。h数组满足一个性质:性质对于i>且Ranki>一定有hi≥hi。为了证明性质我们有必要明确两个事实:IOI国家集训队论文许智磊第页共页设i<n,j<nSuffix(i)和Suffix(j)满足lcp(Suffix(i),Suffix(j)>则成立以下两点:FactSuffix(i)<Suffix(j)等价于Suffix(i)<Suffix(j)。Fact一定有lcp(Suffix(i),Suffix(j))=lcp(Suffix(i),Suffix(j))。看起来很神奇但其实很自然:lcp(Suffix(i),Suffix(j))>说明Suffix(i)和Suffix(j)的第一个字符是相同的设它为α则Suffix(i)相当于α后连接Suffix(i)Suffix(j)相当于α后连接Suffix(j)。比较Suffix(i)和Suffix(j)时第一个字符α是一定相等的于是后面就等价于比较Suffix(i)和Suffix(j)因此Fact成立。Fact可类似证明。于是可以证明性质:当hi≤时结论显然成立因hi≥≥hi。当hi>时也即heightRanki>可见Ranki>因height=。令j=i,k=SARankj。显然有Suffix(k)<Suffix(j)。根据hi=lcp(Suffix(k),Suffix(j))>和Suffix(k)<Suffix(j):由Fact知lcp(Suffix(k),Suffix(i))=hi。由Fact知Rankk<Ranki也就是Rankk≤Ranki。于是根据LCPCorollary有LCP(Ranki,Ranki)≥LCP(Rankk,Ranki)=lcp(Suffix(k),Suffix(i))=hi由于hi=heightRanki=LCP(Ranki,Ranki)最终得到hi≥hi。根据性质可以令i从循环到n按照如下方法依次算出hi:若Ranki=则hi=。字符比较次数为。若i=或者hi≤则直接将Suffix(i)和Suffix(Ranki)从第一个字符开始依次比较直到有字符不相同由此计算出hi。字符比较次数为hi不超过hihi。否则说明i>Ranki>hi>根据性质Suffix(i)和Suffix(Ranki)至少有前hi个字符是相同的于是字符比较可以从hi开始直到某个字符不相同由此计算出hi。字符比较次数为hihi。设SA=p那么不难看出总的字符比较次数不超过npnnhpphihihphihihhnpipi)()()()(££åå==也就是说整个算法的复杂度为O(n)。求出了h数组根据关系式heighti=hSAi可以在O(n)时间内求出height数组于是可以在O(n)时间内求出height数组。IOI国家集训队论文许智磊第页共页结合RMQ方法在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。因为lcp(Suffix(i),Suffix(j))=LCP(Ranki,Rankj)所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。后缀数组的应用下面结合两个例子谈谈如何运用后缀数组。例一多模式串的模式匹配问题给定一个固定待匹配串S长度为n然后每次输入一个模式串P长度为m要求返回P在S中的一个匹配或者返回匹配失败。所谓匹配指某个位置i满足≤i≤nm使得Si(im)=P也即Suffix(i)=mP。我们知道如果只有一个模式串最好的算法就是KMP算法时间复杂度为O(nm)但是如果有多个模式串我们就要考虑做适当的预处理使得对每个模式串进行匹配所花的时间小一些。最简单的预处理莫过于建立S的后缀数组(先在S的后面添加'$')然后每次寻找匹配转化为用二分查找法在SA中找到和P的公共前缀最长的一个后缀判断这个最长的公共前缀是否等于m。这样每次比较P和一个后缀的复杂度为O(m)因为最坏情况下可能比较了m个字符。二分查找需要调用比较的次数为O(logn)因此总复杂度为O(mlogn)于是每次匹配的复杂度从O(nm)变为O(mlogn)可以说改进了不少。可是这样仍然不能令我们满足。前面提到LCP可以增加后缀数组的威力我们来试试用在这个问题上。我们分析原始的二分查找算法大体有以下几步:Step令left=,right=n,maxmatch=。Step令mid=(leftright)(这里“”表示取整除法)。Step顺次比较Suffix(SAmid)和P的对应字符找到两者的最长公共前缀r并判断出它们的大小关系。若r>maxmatch则令maxmatch=r,ans=mid。Step若Suffix(SAmid)<P则令left=mid若Suffix(SAmid)>P则令right=mid若Suffix(SAmid)=P则转至Step。Step若left<right则转至Step否则至Step。Step若maxmatch=m则输出ans否则输出“无匹配”。注意力很快集中在Step如果能够避免每次都从头开始比较Suffix(SAmid)和P的对应字符也许复杂度就可以进一步降低。类似于前面求height数组我们考虑利用以前求得的最长公共前缀作为比较的“基础”避免冗余的字符比较。IOI国家集训队论文许智磊第页共页在比较Suffix(SAmid)和P之前我们先用常数时间计算LCP(mid,ans)然后比较LCP(mid,ans)和maxmatch:情况一:LCP(mid,ans)<maxmatch则说明Suffix(SAmid)和P的最长公共前缀就是LCP(mid,ans)即直接可以确定Step中的r=LCP(mid,ans)所以可以直接比较两者的第r个字符(结果一定不会是相等)就可以确定Suffix(SAmid)和P的大小。这种情况下字符比较次数为次。情况二:LCP(mid,ans)≥maxmatch则说明Suffix(SAmid)和Suffix(SAans)的前maxmatch个字符一定是相同的于是Suffix(SAmid)和P的前maxmatch个字符也是相同的于是比较两者的对应字符可以从第maxmatch个开始最后求出的r一定大于等于原先的maxmatch字符比较的次数为rmaxmatch不难看出Step执行过后maxmatch将等于r。设每次Step执行之后maxmatch值增加的量为∆max。在情况一中∆max=字符比较次数为=∆max在情况二中∆max=rmaxmatch字符比较次数为rmaxmatch也是∆max。综上所述每次Step进行字符比较的次数为∆max。总共的字符比较次数为所有的∆max累加起来再加上Step执行的次数。所有∆max累加的结果显然就是最后的maxmatch值不会超过len(P)=m而Step执行的次数为O(logn)因此总共的字符比较次数为O(mlogn)。而整个算法的复杂度显然和字符比较次数同阶为O(mlogn)。至此问题得到圆满解决通过O(nlogn)的时间进行预处理(构造后缀数组、名词数组计算height数组RMQ预处理)之后就可以在O(mlogn)的时间内对一个长度为m的模式串P进行模式匹配这仅仅是在读入P的复杂度上附加了logn的复杂度是非常优秀的。例二最长回文子串问题一个回文串是指满足如下性质的字符串u:ui=ulen(u)i对所有的≤i≤len(u)。也就是说回文串u是关于u的中间位置“对称”的。按照回文串的长度的奇偶性把回文串分为两类:长度为奇数的回文串称为奇回文串长度为偶数的回文串称为偶回文串。设想我们在回文串u的“中心位置”划一条直线显然对于奇回文串这条线划在中间一个字符(u(len(u)))上而对于偶回文串这条线划在中间的两个字符(ulen(u)和ulen(u))之间。以下是两个例子:回文串里的字符是关于这条中心线对称分布的。中心线左边的字符串颠倒过来等于右边的字符串我们称之为“反射相等”。字符串T的回文子串指的是T的子串中同时又是回文串的那些字符串。T的回文子串中长度最大的称为最长回文子串。类似地定义奇(偶)回文子串和最长奇(偶)回文子串。abcbaalfflcacIOI国家集训队论文许智磊第页共页最长回文子串问题是给定一个字符串T求T的最长回文子串简便起见只要求给出最长回文子串的长度即可。下面我们分析求最长奇回文串的方法最长偶回文串的求法是类似的。因为每个奇回文子串一定有一个中心位置(是整个回文串的中间一个字符)这个中心位置是T串的某个字符所以我们首先枚举定下它的中心位置。对于一个固定的中心位置i可能存在多个以Ti为中心的奇回文子串但是它们满足一个性质:奇回文串在Ti左边的部分和右边的部分长度相等而且关于Ti对称即跟Ti距离相同的左右两个字符对应相等。那么任何一个以Ti为中心的奇回文子串都可以表示为Tirir,r≥。可以看出r越大这个以Ti为中心的奇回文串也就越长。因此只要能够找到最大的一个r使得Tiri和Tiir关于Ti对称也就求出了以Ti为中心的奇回文子串中最长的一个(可以看出也一定只有一个)。如果枚举i从到len(T)求出以每个Ti为中心的奇回文子串中的最长者这些最长者里面长度最大的一个也就是整个T串的最长奇回文子串。如何求以Ti为中心的奇回文子串中的最长者呢?首先当r=时Ti单个字符本身构成一个奇回文子串它的长度为。下面我们考虑将r不断增加假设当r=k时Tirir构成奇回文子串也就是说Tiri和Tiir反射相等当r=k时我们比较Ti(k)与Tik这两个字符若相等则说明Ti(k)i与Tiik是关于Ti对称的(因为根据假设Tiki与Tiik已经关于Ti对称)于是r可以扩展到k。如果Ti(k)和Tik不同则说明Ti(k)i和Tiik不对称并且对任何r'>kTir'i和Tiir'也不可能关于Ti对称了所以r最大只能到k。我们把r递增的过程称为向两边扩展扩展一次就可以把以Ti为中心的奇回文子串的长度加。最后r扩展到的最大值决定了以Ti为中心的奇回文子串中的最长者的长度(为r)。设len(T)=m如果用依次比较对应字符的方法来求向两边扩展的最大值则最多可能比较m个字符。由于要枚举每个位置作为中心向两边扩展所以最坏情况下总的复杂度可以达到O(m)不很理想。下面优化算法的核心部分以一个位置为中心求向两边扩展的最大值。在T串的末尾添加一个特殊字符'#'规定它不等于T的任何一个字符然后把T串颠倒接在'#'后在T'串后再添加特殊字符'$'规定它小于前面的任何一个字符拼接后形成的串称为S串。不难看出T串中任何一个字符都可在T'中对称地找到一个相同的字符。如果都用S里的字符来表示Sm是T串Smm是T'串则每个Si(≤i≤m)关于'#'对称的字符是Smi。这样原先T串里面的一个子串Sij(≤i≤j≤m)关于'#'也可以对称地找到一个反射相等的子串Smjmi。现在我们定下T串的某个位置Si为中心假设向两边扩展到了ir和ir那么Siri和Siir是反射相等的Si可以在T'中找到对称的字符Smi设i'=mi则Siri也可以在T'中找到对称的子串Si'i'rbanana#ananab$TT'ii'=miIOI国家集训队论文许智磊第页共页那么Siir和Si'i'r同时与Siri反射相等也就是说Siir=Si'i'r。又因为Si=Si'故Siir=Si'i'r。也就是说Suffix(i)=rSuffix(i')。现在要求r尽量大也就是求max{r|Suffix(i)=rSuffix(i')}不难看出这里r=LCP(i,i')。上面的推理还存在一个问题即求出的LCP(i,i')还只能看作r的一个上界还不能当成r的最大值因为还需要证明给出Suffix(i)和Suffix(i')的最长公共前缀一定可以反过来在T串中找到相应的以i为中心的回文串这个证明与前面的推理类似只是需要注意一点:这里利用到了'#'这个特殊字符避免了潜在的LCP(i,i')超过实际的r最大值的危险。这个证明留给读者自行完成。总之我们已经确定求以Ti为中心向两边扩展的最大值等价于求LCP(i,i')根据前面后缀数组和LCP的相关内容这一步操作可以在常数时间内完成只要我们预先花费O(nlogn)的复杂度计算后缀数组、height数组和进行预处理。其中n=len(S)=m。现在每次求以一个位置Ti为中心的回文子串中的最长者的长度可以在常数时间内完成我们枚举i从到m依次求出所有的这些最长者记录其中最大的一个的长度就是所要求的最长奇回文子串的长度。由于对每个中心花费时间为常数所以总的复杂度为O(m)。因此整个算法的复杂度是O(nlognm)=O(mlog(m)m)=O(mlogm)是非常优秀的算法比之前的平方级算法大为改进。后缀数组与后缀树的比较通过上面的两个例子相信读者已经对后缀数组的强大功能有所了解另一种数据结构后缀树也可以用在这些问题中那么后缀数组和后缀树有什么区别和联系呢?我们来比较一下:首先后缀数组比较容易理解也易于编程实现而且不像后缀树那样需要涉及到指针操作所以调试起来比较方便。第二后缀数组占用的空间比后缀树要小刚才分析中我们并没有提到空间复杂度的问题这里简单说一下:后缀数组SA和名词数组Rank都只需要n个整数的空间而在由Rankk计算出SAk的过程中需要用两个一维数组来辅助完成各占n个整数的空间滚动地进行操作整个算法只需要这四个一维数组和常数个辅助变量因此总的空间占用为n个整数。而后缀树通常有n个以上节点通常每个节点要两个整数(即使采用一些技巧至少还是要保存一个整数)每个节点要有两个指针(假设采用儿子兄弟表示方法)因此总共的空间占用至少是n个指针和n个整数(至少是n个整数)。如果采用其他方法表示树状结构需要的空间更大。可以看出后缀数组的空间需求比后缀树小。最后比较它们的复杂度:首先按照字符总数|Σ|把字符集Σ分为三种类型:若|Σ|是一个常数则称Σ为ConstantAlphabet若|Σ|的大小是关于S的长度n的多项式函数则称Σ为IntegerAlphabet若|Σ|没有大小上的限制则称Σ为GeneralAlphabet。IOI国家集训队论文许智磊第页共页显然ConstantAlphbet属于IntegerAlphabet的一种而IntegerAlphabet是GeneralAlphabet的一种。构造后缀数组的复杂度与字符集无关因为它是直接针对GeneralAlphabet的算法。对于普通方法构造后缀树如果用儿子兄弟方式表达树状结构时间复杂度达到O(n*|Σ|)显然对于IntegerAlphabet和GeneralAlphabet都很低效对|Σ|较大的ConstantAlphabet也不适用。解决的方法是用平衡二叉树来保存指向儿子的指针这样复杂度变为O(n*log|Σ|)。可见后缀树在某些情况下相对后缀数组有速度上的优势但是并不明显。对于|Σ|很小的字符串后缀树相比后缀数组的速度优势还是比较可观的。尤其是对于很常见的串。后缀数组实际上可以看作后缀树的所有叶结点按照从左到右的次序排列放入数组中形成的所以后缀数组的用途不可能超出后缀树的范围。甚至可以说如果不配合LCP后缀数组的应用范围是很狭窄的。但是LCP函数配合下的后缀数组就非常强大可以完成大多数后缀树所能完成的任务因为LCP函数实际上给出了任意两个叶子结点的最近公共祖先这方面的内容大家可以自行研究。后缀树和后缀数组都是字符串处理中非常优秀的数据结构不能说一个肯定优于另一个对于不同场合、不同条件的问题我们应该灵活应用精心选择地选择其中较为适合的一个。算法和数据结构都是死的而运用它们的人才是真正的主角对经典的算法和数据结构熟练掌握并适当地运用以发挥它们最大的力量这才是信息学研究和竞赛中最大的智慧也是信息学竞赛的魅力所在。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/11

后缀数组

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利