全部答案

2018-10-27 01:41:41

•   后缀数组
   在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。
    可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀数组的构造方法，最后结合一些例子谈谈后缀数组的应用。 
   基本概念 
   首先明确一些必要的定义: 
   字符集 一个字符集∑是一个建立了全序关系的集合，也就是说，∑中的任意两个不同的元素α和β都可以比较大小，要么αβ)。
    字符集∑中的元素称为字符。 
   字符串 一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S。 
   子串 字符串S的子串S[i。。j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S,S[i 1],。
    。。,S[j]形成的字符串。 
   后缀 后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i。。len(S)]。 
   关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u和v，如果相等则令i加1，否则若uv则认为u>v(也就是vlen(u)或者i>len(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)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) ≤kSuffix(SAk[i 1]),1≤ij时可交换i,j，i=j时可以直接输出结果n-SA 1。 
   直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。
     
   经过仔细分析，我们发现LCP函数有一个非常好的性质: 
   设ip，则 
   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，又由pp不成立，即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≤j1且Rank>1，一定有h≥h[i-1]-1。 
   为了证明性质3，我们有必要明确两个事实: 
   设i1，则成立以下两点: 
   Fact 1 Suffix(i)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≥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)1和Suffix(k)1，Rank>1，h[i-1]>1，根据性质3，Suffix(i)和Suffix(Rank-1)至少有前h[i-1]-1个字符是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h。
    字符比较次数为h-h[i-1] 2。 
   设SA[1]=p，那么不难看出总的字符比较次数不超过 
   也就是说，整个算法的复杂度为O(n)。 
   求出了h数组，根据关系式height=h[SA]可以在O(n)时间内求出height数组，于是 
   可以在O(n)时间内求出height数组。
     
   结合RMQ方法，在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。 
   因为lcp(Suffix(i),Suffix(j))=LCP(Rank,Rank[j])，所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。
    这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。

  全部
  

  杜***

  2018-10-27 01:41:41

  50 33 评论

  分享
  提交评论