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;

　　int i,j,k,p,*t,m=255;

　　for (i = 0; i<= m; i++)//对字符排序不会超过255，根据实际情况m值自定

　　bar[i] = 0;

　　for (i = 0; i< len; i++) bar[Rank_x[i] =s[i]]++;

　　for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

　　for (i = len-1; i>= 0; i--)sa[--bar[Rank_x[i]]] = i;

　　//这段代码用到桶排序思想，就是先进桶，再从不同桶里一个一个往外倒

　　//sa[]保存的是1-前缀排序结果，Rank_x[]保存的是1-前缀时的各位置的排名

　　for (k = 1,p = 1; p < len; k *= 2, m = p)

　　{

　　for (p = 0,i = len - k; i < len;i++) Rank_y[p++] = i;

　　for (i = 0; i< len; i++) if (sa[i]>= k) Rank_y[p++] = sa[i] - k;

　　//这段代码对1-前缀时做第二关键字排序

　　for (i = 0; i< len; i++) result_x[i]= Rank_x[Rank_y[i]];

　　for (i = 0; i<= m; i++) bar[i] =0;

　　for (i = 0; i< len; i++)bar[result_x[i]]++;

　　for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

　　for (i = len-1; i>= 0; i--)sa[--bar[result_x[i]]] = Rank_y[i];

　　//又用到了一次桶排序，注意体会，是在对第二关键字排好序的序列上对

　　//第一关键字进行桶排序求得了新的sa[]，result_x[]保存的是关于第二关键字

　　//排好序的序列的第一关键字排名，为桶排序做好准备

　　for (t = Rank_x,Rank_x = Rank_y,Rank_y= t,p = 1,Rank_x[sa[0]]= 0,i = 1; i

　　Rank[sa[i]] =cmp(Rank_y,sa[i],sa[i-1],k)?p-1:p++;

　　//求新的名次数组，可以发现名次可能一样，当名次各不一样时就是排序完成时。

　　}

　　}