什么是后缀数组 求字符串匹配
后缀数组 在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。 可以说,在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法,以及配合后缀数组的最长公共前缀数组的构造方法,最后结合一些例子谈谈后缀数组的应用。 基本概念 首先明确一些必要的定义: 字符集 一个字符集∑是一个建立了全序关系的集合,也就是说,∑中的任意两个不同的元素...全部
后缀数组 在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。
可以说,在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法,以及配合后缀数组的最长公共前缀数组的构造方法,最后结合一些例子谈谈后缀数组的应用。 基本概念 首先明确一些必要的定义: 字符集 一个字符集∑是一个建立了全序关系的集合,也就是说,∑中的任意两个不同的元素α和β都可以比较大小,要么αβ)。
字符集∑中的元素称为字符。 字符串 一个字符串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的任何两个后缀之间的最长公共前缀。
这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。收起