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++;
//求新的名次数组，可以发现名次可能一样，当名次各不一样时就是排序完成时。
}
}