2011年软考程序员考试复习笔试知识点整理(16)

来源：长理培训发布时间：2017-10-20 14:08:59

20、后缀数组

　　(1)什么是后缀数组呢?

　　直观来说，后缀数组是记录一个字符串的后缀的排名的数组，什么是后缀呢，设一个字符串的长度是len(我们约定字符串下标从0开始，所以到len-1结束，比较符合我们日常编程习惯)，某一位置i的后缀的就是从i开始到len-1结束的字符串，用suffix(i)表示，即对字符串s来说，suffix(i) =s[i,i+1....len-1]，可以发现不同的后缀按字典序排列的名词是不一样的(什么是字典序都应该知道吧)，记录这些后缀按字典序排好的结果的数组就叫后缀数组，一般用sa[]表示，网络上对sa[]的标准定义为：

　　后缀数组：后缀数组SA 是一个一维数组，它保存1..n 的某个排列SA[1]，SA[2]，……，SA[n]，并且保证Suffix(SA[i])< Suffix(SA[i+1])，1≤i

　　另外还要用到排名数组，即某一位置的后缀在所有后缀中的排名的数组，一般用Rank[]表示，容易发现Rank[sa[i]]=i。

　　名次数组：名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的"名次"。

　　简单的说，后缀数组是"排第几的是谁?"，名次数组是"你排第几?"。

　　知道了这些定义，剩下的就是如何构建后缀数组了，可以按照定义来构建，把每个后缀当做一个字符串，用全速排序来排序，不过那样的时间复杂度为O(n*n)，一般用来构建后缀数组用的是倍增算法(Doubling Algorithm)，说到倍增算法，就要说到k-前缀的定义，字符串u的k-前缀就是u的从0开始到k-1的字串，u长度不足k时就是整个字符串u，这样一来我们在比较串s的两个位置i,j的后缀的2k-前缀时，就是比较两个后缀的k-前缀和两个后缀位置+k的k-前缀，显然当k=1时就是对整个串的单字符进行排序，复杂度O(nlogn)，当k>=2时对已排好的k-前缀进行排序，用快排，复杂度O(nlogn)，用基数排序，复杂度O(n)，容易发现k是2倍增的。所以整个过程的时间复杂度就是O(nlongn)。

　　倍增算法构建sa[]的代码如下：

　　#definemax 10000

　　intRx[max],Ry[max],rx[max];

　　intcmp(int *y,int a,int b,int l)

　　{

　　return y[a] == y[b] && y[a+l] +y[b+l];

　　}

　　//对于串约定最后一位是小于串中其他任何元素的元素，这样cmp的时候就不用担心y[a+l]

　　//越界了，因为y[a]= y[b]就暗含了他们长度相等，都没有包含最后一位。

　　voidget_sa(char *s,int *sa)

　　{

　　int len = strlen(s),*Rank_x = Rx,*Rank_y =Ry,bar[max],*result_x = rx;