字符串之后缀数组

《字符串之后缀数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、后缀数组——处理字符串的有力工具作者：罗穗骞２００９年１月　　【摘要】　　后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。本文分两部分。第一部分介绍两种构造后缀数组的方法，重点介绍如何用简洁高效的代码实现，并对两种算法进行了比较。第二部分介绍后缀数组在各种类型题目中的具体应用。　　【关键字】　　字符串，后缀，后缀数组，名次数组，基数排序，　　【正文】一、后缀数组的实现　　本节主要介绍后缀数组的两种

2、实现方法：倍增算法（DoublingAlgorithm）和DC3算法（DifferenceCover），并对两种算法进行了比较。可能有的读者会认为这两种算法难以理解，即使理解了也难以用程序实现。本节针对这个问题，在介绍这两种算法的基础上，还给出了简洁高效的代码。其中倍增算法只有25行，DC3算法只有40行。1.1、基本定义　　子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i]，r[i+1]，...，r[j]形成的字符串。　　后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(

3、i)，也就是Suffix(i)=r[i..len(r)]。　　大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令i加1，否则若u[i]v[i]则认为u>v（也就是vlen(u)或者i>len(v)仍比较不出结果，那么若len(u)len(v)则u>v。　　从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结

4、果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。　　后缀数组：后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1]，SA[2]，……，SA[n]，并且保证Suffix(SA[i])

5、度为n。为了方便比较大小，可以在字符串后面添加一个字符，这个字符没有在前面的字符中出现过，而且比前面的字符都要小。在求出名次数组后，可以仅用O(1)的时间比较任意两个后缀的大小。在求出后缀数组或名次数组中的其中一个以后，便可以用O(n)的时间求出另外一个。任意两个后缀如果直接比较大小，最多需要比较字符n次，也就是说最迟在比较第n个字符时一定能分出“胜负”。1.2、倍增算法　　倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为2k的子字符串进行排序，求出排名，即rank值。k从0开始，每次加1，当2k大于n以后，每个字符开始的长度为2k的子字符串便相当于所有的后缀。并且这些

6、子字符串都一定已经比较出大小，即rank值中没有相同的值，那么此时的rank值就是最后的结果。每一次排序都利用上次长度为2k-1的字符串的rank值，那么长度为2k的字符串就可以用两个长度为2k-1的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为2k的字符串的rank值。以字符串“aabaaaab”为例，整个过程如图2所示。其中x、y是表示长度为2k的字符串的两个关键字。　　具体实现：   intwa[maxn],wb[maxn],wv[maxn],ws[maxn];   intcmp(int*r,inta,intb,intl)   {returnr[a]==r[

7、b]&&r[a+l]==r[b+l];}   voidda(int*r,int*sa,intn,intm)   {       inti,j,p,*x=wa,*y=wb,*t;        for(i=0;i=0;i--)sa[--ws[x[i]]]=i;