下载文档原格式
构造后缀数组的DC3算法实现DC3算法(Difference Cover mod 3)是J. Kärkkäinen和P. Sanders在2003年发表的论⽂ "Simple Linear Work Suffix Array Construction"中描述的线性时间内构造后缀数组的算法。
相对Prefix Doubling（前缀倍增）算法⽽⾔，虽然它的渐进时间复杂度⽐较⼩，但是常数项⽐较⼤。
DC3算法的思想类似于找中位数的median of medians算法（/wiki/Selection_algorithm），它采⽤分治思想: 先⽤递归⽅式对起始下标等于1(mod 3)和2(mod 3)的后缀排序，从⽽将原始的后缀集合⼤⼩缩⼩为2/3，设这些后缀排好序的结果为S12，然后在S12的基础上对起始下标等于0(mod 3)的后缀排序（这⼀步只需作两位数的基数排序，⼀位为0(mod 3)的起始下标，另外⼀位为S12的rank 值），设这⼀步得到的排好序的后缀数组为S0，最后将S0和S12归并（类似于归并排序算法）。
归并过程通过 Difference Cover思想，也是在S12已知的基础上分两个cases得出相邻两个后缀的先后顺序。
实现：/**** Build Suffix Array using DC3/KS Algorithm*** Copyright (c) 2011 ljs (/ljsspace/)* Licensed under GPL (/licenses/gpl-license.php)** @author ljs* 2011-07-18**/public class DC3 {public static final char MAX_CHAR = '\u00FF';class Suffix{int[] sa;//Note: the p-th suffix in sa: SA[rank[p]-1]];//p is the index of the array "rank", start with 0;//a text S's p-th suffix is S[p..n], n=S.length-1.int[] rank;boolean done;public Suffix(int[] sa,int[] rank){this.sa = sa;this.rank = rank;}}//a prefix of suffix[isuffix] represented with digitsclass Tuple{int isuffix; //the p-th suffixint[] digits;public Tuple(int suffix,int[] digits){this.isuffix = suffix;this.digits = digits;}public String toString(){StringBuffer sb = new StringBuffer();sb.append(isuffix);sb.append("(");for(int i=0;i<digits.length;i++){sb.append(digits[i]);if(i<digits.length-1)sb.append("-");}sb.append(")");return sb.toString();}}//d: the digit to do countingsort//max: A value's range is 0...maxprivate void countingSort(int d,Tuple[] tA,Tuple[] tB,int max){//init the counter arrayint[] C = new int[max+1];for(int i=0;i<=max;i++){C[i] = 0;}//stat the countfor(int j=0;j<tA.length;j++){C[tA[j].digits[d]]++;}//process the counter array Cfor(int i=1;i<=max;i++){C[i]+=C[i-1];}//distribute the valuesfor(int j=tA.length-1;j>=0;j--){//C[A[j]] <= A.lengthtB[--C[tA[j].digits[d]]]=tA[j];}}//tA: input//tB: output for rank caculationprivate void radixSort(Tuple[] tA,Tuple[] tB,int max,int digitsLen){int len = tA.length;int digitsTotalLen = tA[0].digits.length;for(int d=digitsTotalLen-1,j=0;j<digitsLen;d--,j++){this.countingSort(d, tA, tB, max);//assign tB to tAif(j<digitsLen-1){for(int i=0;i<len;i++){tA[i] = tB[i];}}}}//max is the maximum value in any digit of TA.digits[], used for counting sort //tA: input//tB: the place holder, reused between iterationsprivate Suffix rank(Tuple[] tA,Tuple[] tB,int max,int digitsLen){int len = tA.length;radixSort(tA,tB,max,digitsLen);int digitsTotalLen = tA[0].digits.length;//caculate rank and saint[] sa = new int[len];sa[0] = tB[0].isuffix;int[] rank = new int[len+2]; //add 2 for sentinelrank[len]=1;rank[len+1] = 1;int r = 1; //rank starts with 1rank[tB[0].isuffix] = r;for(int i=1;i<len;i++){sa[i] = tB[i].isuffix;boolean equalLast = true;for(int j=digitsTotalLen-digitsLen;j<digitsTotalLen;j++){if(tB[i].digits[j]!=tB[i-1].digits[j]){equalLast = false;break;}}if(!equalLast){r++;}rank[tB[i].isuffix] = r;}Suffix suffix = new Suffix(sa,rank);//judge if we are doneif(r==len){suffix.done = true;}else{suffix.done = false;}return suffix;}private int[] orderSuffixes(Tuple[] tA,Tuple[] tB,int max,int digitsLen){int len = tA.length;radixSort(tA,tB,max,digitsLen);//caculate rank and saint[] sa = new int[len];for(int i=0;i<len;i++){sa[i] = tB[i].isuffix;}return sa;}//rank needs sentinel: len+2public Suffix reduce(int[] rank,int max){int len = rank.length - 2;int n1 = (len+1)/3;Tuple[] tA = new Tuple[n1+n2];Tuple[] tB = new Tuple[n1+n2];for(int i=0,j=1;i<n1;i++,j+=3){int r1 = rank[j];int r2 = rank[j+1];int r3 = rank[j+2];tA[i] = new Tuple(i,new int[]{r1,r2,r3});}for(int i=n1,j=2;i<n1+n2;i++,j+=3){int r1 = rank[j];int r2 = rank[j+1];int r3 = rank[j+2];tA[i] = new Tuple(i,new int[]{r1,r2,r3});}return rank(tA,tB,max,3);}public int[] skew(int[] rank,int max){int len = rank.length - 2;//step 1: caculate sa12Suffix suffixT12 = reduce(rank,max);int[] sa12 = null;if(!suffixT12.done){int[] rankT12 = suffixT12.rank;int maxT12 = rankT12[suffixT12.sa[suffixT12.sa.length-1]]; sa12 = skew(rankT12,maxT12);// debug for string: GACCCACCACC#//s12 = new Suffix();//s12.rank = new int[]{3,6,5,4,7,2,1,1,1};//s12.sa = new int[]{7,6,5,0,3,2,1,4};//s12.done =true;}else{sa12 = suffixT12.sa;}//index conversion for sa12int n1 = (len+1)/3;for(int j=0;j<sa12.length;j++){if(sa12[j]<n1){sa12[j] = 1 + 3*sa12[j];}else{sa12[j] = 2 + 3*(sa12[j]-n1);}}//recaculate rank for sa12int[] rank12 = new int[len+2];rank12[len] = 1;rank12[len+1] = 1;for(int k=0;k<sa12.length;k++){rank12[sa12[k]] = k+1;}//step 2: caculate sa0int n0=(len+2)/3;Tuple[] tA = new Tuple[n0];Tuple[] tB = new Tuple[n0];for(int i=0,j=0;i<n0;i++,j+=3){int r1 = rank[j];int r2 = rank12[j+1];tA[i] = new Tuple(i,new int[]{r1,r2});}int max12 = rank12[sa12[sa12.length-1]];int[] sa0 = orderSuffixes(tA,tB,max<max12?max12:max,2); //index conversion for sa0for(int j=0;j<n0;j++){sa0[j] = 3*sa0[j];}//step 3: merge sa12 and sa0int[] sa = new int[len];int i=0,j=0;int k=0;while(i<sa12.length && j<sa0.length){int p = sa12[i];int q = sa0[j];if(p%3==1){if(rank[p]<rank[q]){sa[k++] = p;i++;}else if(rank[p]>rank[q]){sa[k++] = q;j++;}else{if(rank12[p+1]<rank12[q+1]){sa[k++] = p;i++;}else{sa[k++] = q;j++;}}}else{//case 2if(rank[p]<rank[q]){sa[k++] = p;i++;}else if(rank[p]>rank[q]){sa[k++] = q;j++;}else{if(rank[p+1]<rank[q+1]){sa[k++] = p;i++;}else if(rank[p+1]>rank[q+1]){sa[k++] = q;j++;}else{if(rank12[p+2]<rank12[q+2]){sa[k++] = p;i++;}else{sa[k++] = q;j++;}}}}}for(int m=i;m<sa12.length;m++){sa[k++] = sa12[m];}for(int m=j;m<sa0.length;m++){sa[k++] = sa0[m];}return sa;}//Precondition: the last char in text must be less than other chars. public Suffix solve(String text){if(text == null)return null;int len = text.length();if(len == 0) return null;char base = text.charAt(len-1); //the smallest charTuple[] tA = new Tuple[len];Tuple[] tB = new Tuple[len]; //placeholderfor(int i=0;i<len;i++){tA[i] = new Tuple(i,new int[]{0,text.charAt(i)-base});}Suffix suffix = rank(tA,tB,MAX_CHAR-base,1);int max = suffix.rank[suffix.sa[len-1]];int[] sa = skew(suffix.rank,max);//caculate rank for result suffix arrayint[] r = new int[len];for(int k=0;k<sa.length;k++){r[sa[k]] = k+1;}return new Suffix(sa,r);}public void report(Suffix suffix){int[] sa = suffix.sa;int[] rank = suffix.rank;int len = sa.length;System.out.println("suffix array:");for(int i=0;i<len;i++){System.out.format(" %s", sa[i]);}System.out.println();System.out.println("rank array:");for(int i=0;i<len;i++){System.out.format(" %s", rank[i]);}System.out.println();}public static void main(String[] args) {String text = "GACCCACCACC#";DC3 dc3 = new DC3();Suffix suffix = dc3.solve(text);System.out.format("Text: %s%n",text);dc3.report(suffix);text = "mississippi#";dc3 = new DC3();suffix = dc3.solve(text);System.out.format("Text: %s%n",text);dc3.report(suffix);text = "abcdefghijklmmnopqrstuvwxyz#";dc3 = new DC3();suffix = dc3.solve(text);System.out.format("Text: %s%n",text);dc3.report(suffix);text = "yabbadabbado#";dc3 = new DC3();suffix = dc3.solve(text);System.out.format("Text: %s%n",text);dc3.report(suffix);text = "DFDLKJLJldfasdlfjasdfkldjasfldafjdajfdsfjalkdsfaewefsdafdsfa#";dc3 = new DC3();suffix = dc3.solve(text);System.out.format("Text: %s%n",text);dc3.report(suffix);}}测试：Text: GACCCACCACC#suffix array:11 8 5 1 10 7 4 9 6 3 2 0rank array:12 4 11 10 7 3 9 6 2 8 5 1Text: mississippi#suffix array:11 10 7 4 1 0 9 8 6 3 5 2rank array:6 5 12 10 4 11 9 3 87 2 1Text: abcdefghijklmmnopqrstuvwxyz#suffix array:27 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26rank array:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1Text: yabbadabbado#suffix array:12 1 6 4 9 3 8 2 7 5 10 11 0rank array:13 2 8 6 4 10 3 9 7 5 11 12 1Text: DFDLKJLJldfasdlfjasdfkldjasfldafjdajfdsfjalkdsfaewefsdafdsfa#suffix array:60 0 2 1 5 7 4 6 3 59 47 54 30 34 41 17 11 25 53 29 33 9 19 23 13 56 44 37 50 48 58 46 10 55 36 39 15 31 20 27 51 40 16 24 32 35 43 21 28 8 22 14 42 52 18 12 57 45 38 26 49rank array:2 43 9 7 5 8 6 50 22 33 17 56 25 52 37 43 16 55 23 39 48 51 24 44 18 60 40 49 20 13 38 45 21 14 46 35 28 59 36 42 15 53 47 27 58 32 11 30 61 29 41 54 19 12 34 26 57 31 10 1。
【字符串】后缀数组后缀排序倍增算法n字符串的长度。
m当前后缀（离散化后）的值域。
对于char可以跳过离散化，初值取128即可，对于int要离散化，初值取n即可，初值要保证覆盖整个值域。
sa[i]排名为i的后缀的起始位置。
rk[i]起始位置为i的后缀的排名。
验证：const int MAXN = 1000000 + 10;int n, m, ct[MAXN], tp[MAXN];int sa[MAXN], rk[MAXN], ht[MAXN];void RadixSort() {for(int i = 0; i <= m; ++i)ct[i] = 0;for(int i = 1; i <= n; ++i)++ct[rk[i]];for(int i = 1; i <= m; ++i)ct[i] += ct[i - 1];for(int i = n; i >= 1; --i)sa[ct[rk[tp[i]]]--] = tp[i];}bool Compare(int i, int j, int l) {if(tp[sa[i]] == tp[sa[j]]) {if(sa[i] + l <= n && sa[j] + l <= n) {if(tp[sa[i] + l] == tp[sa[j] + l])return 1;}}return 0;}void SuffixSort(char *s) {n = strlen(s + 1), m = 128;for(int i = 1; i <= n; ++i) {rk[i] = s[i];tp[i] = i;}RadixSort();for(int l = 1;; l <<= 1) {m = 0;for(int i = n - l + 1; i <= n; ++i)tp[++m] = i;for(int i = 1; i <= n; ++i) {if(sa[i] > l)tp[++m] = sa[i] - l;}RadixSort();swap(tp, rk);m = 1;rk[sa[1]] = 1;for(int i = 2; i <= n; ++i) {if(Compare(i - 1, i, l) == 0)++m;rk[sa[i]] = m;}if(m == n)break;}}最⼩循环表⽰把字符串S循环移动，找字典序最⼩的那个表⽰。
后缀数组实现的倍增算法和DC3算法[cpp] view plaincopyprint?/************************************************数据结构：后缀数组(Suffix_Array);子串:字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串;后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串;字符串r的从第i个字符开始的后缀表示为Suffix(i),也就是Suffix(i)=r[i...len(r)];后缀数组SA:后缀数组保存的是一个字符串的所有后缀的排序结果;其中SA[i]保存的是字符串所有的后缀中第i小的后缀的开头位置;名次数组Rank：名次数组Rank[i]保存的是后缀i在所有后缀中从小到大排列的“名次”;后缀数组是"排第几的是谁",名次数组是"排第几",即后缀数组和名次数组为互逆运算;(1)倍增算法:用倍增的方法对每个字符开始的长度为2^k的子字符串进行排序，求出排名，即rank值。
k从0开始，每次加1，当2^k大于n以后，每个字符开始的长度为2^k的子字符串便相当于所有的后缀。
并且这些子字符串都一定已经比较出大小，即rank值中没有相同的值，那么此时的rank值就是最后的结果。
每一次排序都利用上次长度为2^k-1的字符串的rank值，那么长度为2^k的字符串就可以用两个长度为2^k-1的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为2^k的字符串的rank值。
(2)DC3算法：①先将后缀分成两部分，然后对第一部分的后缀排序;②利用①的结果，对第二部分的后缀排序;③将①和②的结果合并，即完成对所有后缀排序;时间复杂度：倍增算法的时间复杂度为O(nlogn),DC3算法的时间复杂度为O(n);从常数上看，DC3算法的常数要比倍增算法大;空间复杂度：倍增算法和DC3算法的空间复杂度都是O(n);倍增算法所需数组总大小为6n,DC3算法所需数组总大小为10n;RMQ(Range Minimum/Maximum Query)问题：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。
后缀数组hdu6704题意:查询l-r之间的子串第k次出现的位置一个子串必定是某个后缀的前缀。
排序相邻的后缀他们的前缀一定最相似。
所以全部的一种子串必定是一些排序相邻的后缀的公共前缀。
从l开始的子串，则从rank[l]开始看，两侧height保证大于子串长度，能延伸多长，则证明有多少个这种子串。
我们用ST表维护出height的最小值，然后通过最小值二分即可，边界有些棘手。
然后我们就得到了一个height不小于子串长度的连续区间，这个区间是以原后缀的字典序排序的。
而同时，sa数组下标为排序，值为原串位置。
所以我们对这个区间在sa数组上做主席树，求第k大，即为第k个子串出现的位置#include<bits/stdc++.h>using namespace std;typedef long long ll;const int INF=0x3f3f3f3f;const int N=1e5+5;char s[N];int sa[N],t[N],t2[N],c[N],n,m;//c是一个桶，sa是后缀数组，sa[i]表示排名第i的是第几个串//x表示rank，x[i]表示第i个串的排名，也是第一关键字//y[i]表示第二关键字排名第i的是第几个串int height[N],rk[N],d[N][30];int root[N],cnt;struct node{int l,r,sum;}T[N*40];void build_sa(int m){int i,*x=t,*y=t2;//基数排序for(int i=1;i<=m;i++)c[i]=0;//清空桶for(i=1;i<=n;i++){//一开始的rank为第一个字符的大小，可以用ascii码表示，并加入桶c[x[i]=s[i]]++;}for(i=2;i<=m;i++){//前缀和，c[i]可以表示前面有多少个比他大c[i]+=c[i-1];}for(i=n;i>=1;i--){sa[c[x[i]]--]=i;//更新sa}for(int k=1;k<=n;k<<=1)//通过第一位依次倍增出每一位{int p=0;//直接利用sa数组排序第二关键字for(i=n-k+1;i<=n;i++){y[++p]=i;//第n-k到第n个串没有后面的后缀，排在最前面}for(i=1;i<=n;i++){//加入排名第i的是第j个串，此时这个串就是j-k个串的右半部分，也就是第二关键字的排名直接可以通过sa获得if(sa[i]>k)y[++p]=sa[i]-k;}//基数排序第一关键字for(i=1;i<=m;i++)c[i]=0;for(i=1;i<=n;i++)c[x[y[i]]]++;for(i=2;i<=m;i++)c[i]+=c[i-1];for(i=n;i>=1;i--){sa[c[x[y[i]]]--]=y[i];//通过先把第二关键字大的先搞出来，可以实现双关键字排序}//根据sa和y数组计算新的x数组swap(x,y);p=1;x[sa[1]]=1;//通过sa更新x，其中如果两个串完全相同，那么rank，也就是x也相同for(i=2;i<=n;i++){x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;}if(p>=n)break;m=p;}}void get_Height(){int i,j,k=0;for(i=1;i<=n;i++){rk[sa[i]]=i;}for(i=1;i<=n;i++){if(rk[i]==1)continue;if(k)k--;j=sa[rk[i]-1];while(s[i+k]==s[j+k]&&(i+k<=n)&&(j+k<=n))k++;height[rk[i]]=k;}}void RMQ_init(){for(int i=1;i<=n;i++)d[i][0]=height[i];for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);}}}int RMQ(int L,int R){int k=0;while((1<<(1+k))<=R-L+1) k++;return min(d[L][k],d[R-(1<<k)+1][k]);}int LCP(int x,int y){int l=rk[x],r=rk[y];if(l>r)swap(l,r);if(l==r)return n-sa[l];return RMQ(l+1,r);}int getL(int l,int r){int left=1,right=rk[l],len=r-l+1;int ans=rk[l];while(left<=right){int mi=(left+right)>>1;if(LCP(sa[mi],l)<len)left=mi+1;else{right=mi-1;ans=mi;}}return ans;}int getR(int l,int r){int ans=rk[l];int left=rk[l],right=n,len=r-l+1;while(left<=right){int mi=(left+right)>>1;if(LCP(sa[mi],l)<len){right=mi-1;}else{left=mi+1;ans=mi;}}return ans;}void update(int l,int r,int pre,int &now,int pos) {T[++cnt]=T[pre];now=cnt;T[cnt].sum++;if(l==r)return;int m=(l+r)>>1;if(pos<=m)update(l,m,T[pre].l,T[now].l,pos);else update(m+1,r,T[pre].r,T[now].r,pos);}int query(int l,int r,int pre,int now,int k){if(l==r)return l;int m=(l+r)>>1;int sum=T[T[now].l].sum-T[T[pre].l].sum;if(k<=sum)return query(l,m,T[pre].l,T[now].l,k);else return query(m+1,r,T[pre].r,T[now].r,k-sum);}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t,q;m='z'+1;cin>>t;while(t--){cin>>n>>q;cin>>s+1;build_sa('z'+1);get_Height();RMQ_init();cnt=0;for(int i=1;i<=n;i++){update(1,n,root[i-1],root[i],sa[i]);}while(q--){int l,r,k;cin>>l>>r>>k;int L=getL(l,r);int R=getR(l,r);if(R-L+1<k)cout<<-1<<endl;else cout<<query(1,n,root[L-1],root[R],k)<<endl;}}}。
为什么学后缀数组后缀数组是一个比较强大的处理字符串的算法，是有关字符串的基础算法，所以必须掌握。
学会后缀自动机(SAM)就不用学后缀数组(SA)了？不，虽然SAM看起来更为强大和全面，但是有些SAM解决不了的问题能被SA解决，只掌握SAM是远远不够的。
……而下面是我对后缀数组的一些理解构造后缀数组——SA先定义一些变量的含义Str：需要处理的字符串(长的为Len)Suffix[i] ：Str下标为i ~ Len的连续子串(即后缀)Rank[i] : Suffix[i]在所有后缀中的排名SA[i] : 满足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名为i的后缀为Suffix[SA[i]] (与Rank是互逆运算)好，来形象的理解一下后缀数组指的就是这个SA[i],有了它，我们就可以实现一些很强大的功能(如不相同子串个数、连续重复子串等)。
如何快速的到它，便成为了这个算法的关键。
而SA和Rank是互逆的，只要求出任意一个，另一个就可以O(Len)得到。
现在比较主流的算法有两种，倍增和DC3，在这里，就主要讲一下稍微慢一些，但比较好实现以及理解的倍增算法(虽说慢，但也是O(Len logLen))的。
进入正题——倍增算法倍增算法的主要思想：对于一个后缀Suffix[i],如果想直接得到Rank 比较困难，但是我们可以对每个字符开始的长度为2k的字符串求出排名，k从0开始每次递增1(每递增1就成为一轮)，当k大于Len时，所得到的序列就是Rank，而SA也就知道了。
O(logLen)枚举k这样做有什么好处呢？设每一轮得到的序列为rank(注意r是小写，最终后缀排名Rank是大写)。
有一个很美妙的性质就出现了！第k轮的rank可由第k - 1轮的rank快速得来!为什么呢？为了方便描述，设SubStr(i, len)为从第i个字符开始，长度为len的字符串我们可以把第k轮SubStr(i,2k)看成是一个由SubStr(i,2k−1)和SubStr(i +2k−1,2k−1)拼起来的东西。
窗外一叶？后缀树与后缀数组本文系转载：/post/hj7cv6m后缀树和后缀数组简直就是ACM 选手必备的知识啊，我已经在两次比赛中碰到过相关的问题了。
我甚至还写过一篇应用的文章，可是我真是井底之蛙啊，那时我还不知道这个叫后缀数组，还有更好的构造算法，还有很多的应用。
最近终于好好在这方面扫了个盲，在此小小地总结一下。
假设有一个长度为 n 的字符串T[0 … n)；S(i) 表示 T 的从下标 i 开始的后缀，即T[i … n)。
那么 T 的后缀数组就是把 S(i) ~ S(n – 1) 这n 个后缀按字典序排好序的一个数组。
它对于查找T 的子串之类的问题是很有用的。
问题就在于怎样快速地把这些后缀排好序。
最简单的方法就是把所有S(i) 快速排序。
快速排序本身的时间是O(n log n)，但是由于排序的对象是一个个字符串，所以每次比较的时间在最差情况下都会变成线性的（也就是 O(n) 的），因此总的时间在最差情况下可能会升到O(n2) 左右，这就很慢了。
对此，我学到了三个更快的算法。
1. Ukkonen 算法Ukkonen 算法先用 O(n) 的时间构造一棵后缀树，然后再用 O(n) 的时间从后缀树得到后缀数组。
在这个网址，介绍了作者Esko Ukkonen，并列出了他的一些论文；其中的一篇《On-line construction of suffix-trees》是可以下载的，里面就讲解了什么是后缀树，怎样在 O(n) 的时间内构造它，以及怎样从它得到后缀数组。
不过我一开始还没发现这篇论文，我是从Dan Gusfield 的《Algorithms on Strings, Trees and Sequences –COMPUTER SCIENCE AND COMPUTATIONAL BIOLOGY》这本书里学到这个算法的。
这本书在中国没的卖，想买的话，可以找代购网站去Amazon 买。
我是在 eMule 上搜到并下载的。
后缀数组之倍增算法⾸先说明：后缀数组的构建在⽹上有多种⽅法：朴素的n*n*logn，还有倍增n*logn的,还有3*n的DC3算法，当然还有DC算法。
这个算法学习⾃林厚丛⽼师的《⾼级数据结构》，代码较长，⽽且常数也⽐较⼤，但是是我这种笨⼈可以理解的。
如有⼈想学短⽽快的可以学习《罗穗骞后缀数组 ---处理字符串的有⼒⼯具》。
顺便说⼀下，罗⼤神的算法书写的的确很短⼩也漂亮，可惜我看不懂。
说⼀下学习的⼼路历程吧！最开始想学后缀树，道理看明的了，可是⼀看代码实在是太长了（可能是我找的模版不对吧）。
后来看到后缀数组的功能也不错，可以实现后缀树的很多功能，于是转向后缀数组。
于是向林⼤神学习，可是在他漂亮的代码映照下的是我愚笨的脑袋，最后是林厚丛⽼师救了我。
感谢林⽼师学习前的准备：1、后缀数组的各种基本概念 后缀：字符串中从第i个开始到它的最后⼀个。
如字符串abcde。
则bcde、cde、de、e都是他的后缀，当然他本⾝也是⾃⼰的后缀。
后缀数组：有两种sa数组和rank数组。
sa[i]表⽰把字符串的所有后缀排序后排第i的是以第⼏个字母开头的后缀。
rank[i]表⽰以第i个字母开头的后缀在后缀的排序中排第⼏。
2、计数排序和基数排序（可以百度⼀下） 计数排序也就是桶排，时间复杂度O(n)1 #include <iostream>2using namespace std;3const int MAXN = 100000;4const int k = 1000; // range5int a[MAXN], c[MAXN], ranked[MAXN];67int main() {8int n;9 cin >> n;10for (int i = 0; i < n; ++i) {11 cin >> a[i];12 ++c[a[i]];13 }14for (int i = 1; i < k; ++i)15 c[i] += c[i-1];16for (int i = n-1; i >= 0; --i)17 ranked[--c[a[i]]] = a[i];//如果是i表达的是原数标号，a[i]就是排序后的正确序列18for (int i = 0; i < n; ++i)19 cout << ranked[i] << endl;20return0;21 }View Code 基数排序，也称桶⼦排序(注意和上⾯的区分)，实际上是分关键安排序。
最长公共⼦串问题的后缀数组解法[最长公共⼦串]最长公共⼦串(Longest Common Substring ,简称LCS)问题，是指求给定的⼀组字符串长度最⼤的共有的⼦串的问题。
例如字符串”abcb”,”bca”,”acbc”的LCS就是”bc”。
求多串的LCS，显然穷举法是极端低效的算法。
改进⼀些的算法是⽤⼀个串的每个后缀对其他所有串进⾏部分匹配，⽤KMP算法，时间复杂度为O(N*L^2)，其中N为字符串个数，L为每个串的长度。
更优秀的有⼴义后缀树的⽅法，时间可以达到 O(N*L)。
本⽂介绍⼀种基于后缀数组的LCS解法，利⽤⼆分查找技术，时间复杂度可以达到O(N*L*logL)。
[最长公共⼦串问题的后缀数组解法]关于后缀数组的构建⽅法以及Height数组的性质，本⽂不再具体介绍，可以参阅IOI国家集训队2004年论⽂《后缀数组》(许智磊)和IOI国家集训队2009年论⽂《后缀数组——处理字符串的有⼒⼯具》(罗穗骞)。
回顾⼀下后缀数组，SA[i]表⽰排名第i的后缀的位置，Height[i]表⽰后缀SA[i]和SA[i-1]的最长公共前缀(Longest Common Prefix,LCP)，简记为Height[i]=LCP(SA[i],SA[i-1])。
连续的⼀段后缀SA[i..j]的最长公共前缀，就是H[i-1..j]的最⼩值，即LCP(SA[i..j])=Min(H[i-1..j])。
求N个串的最长公共⼦串，可以转化为求⼀些后缀的最长公共前缀的最⼤值，这些后缀应分属于N个串。
具体⽅法如下：设N个串分别为S1,S2,S3,…,SN，⾸先建⽴⼀个串S，把这N个串⽤不同的分隔符连接起来。
S=S1[P1]S2[P2]S3…SN-1[PN-1]SN，P1,P2,…PN-1应为不同的N-1个不在字符集中的字符，作为分隔符(后⾯会解释为什么)。
接下来，求出字符串S的后缀数组和Height数组，可以⽤倍增算法，或DC3算法。
后缀数组、不重复子串Distinct Substrings题目大意：给出一个字符串，问它的不重复子串有多少个。
两题是一样的，除了字符串长度..分析：用后缀数组可以轻松解决。
因为这个字符串的每个子串必然是某个后缀的前缀，先用后缀数组求出sa和height，那么对于sa[k]，它有n-sa[k]个子串，其中有height[k]个是和上一个后缀重复的，所以要减去。
所以用后缀数组求解的时间复杂度是O(n)，后缀数组要是用倍增算法是O(nlog2n)，效率很高。
note：wa了一次，主要原因是忘了a[n]=0这个关键的初值...PS：各位大牛对我的差劲的c++代码有什么看法可以尽管喷哈！codes:#include<iostream>#include<cstring>using namespace std;const long maxn=1010;long wn[maxn],wa[maxn],wb[maxn],wv[maxn],a[maxn],sa[maxn],rank[maxn],height[maxn]; char r[maxn];long cmp(long *r,long a,long b,long l){return r[a]==r[b]&&r[a+l]==r[b+l];}void da(long *r,long *sa,long n,long m){long i,j,p,*x=wa,*y=wb,*t;for (i=0;i<m;i++) wn[i]=0;for (i=0;i<n;i++) wn[x[i]=r[i]]++;for (i=1;i<m;i++) wn[i]+=wn[i-1];for (i=n-1;i>=0;i--) sa[--wn[x[i]]]=i;for (p=1,j=1;p<n;j*=2,m=p){for (p=0,i=n-j;i<n;i++) y[p++]=i;for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;for (i=0;i<m;i++) wn[i]=0;for (i=0;i<n;i++) wn[wv[i]=x[y[i]]]++;for (i=1;i<m;i++) wn[i]+=wn[i-1];for (i=n-1;i>=0;i--) sa[--wn[wv[i]]]=y[i];for (t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return;}void calheight(long *r,long *sa,long n){long i,j,k=0;for (i=1;i<=n;i++) {rank[sa[i]]=i;height[i]=0;}for (i=0;i<n;height[rank[i++]]=k)for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);return;}int main(){long t,i;cin >> t;while (t--){cin >> r;long n=strlen(r);for (int i=0;i<n;i++) a[i]=static_cast<int>(r[i]);a[n]=0;da(a,sa,n+1,256);calheight(a,sa,n);long sum=0;for (i=1;i<=n;i++) sum+=n-sa[i]-height[i];cout << sum << endl;}return 0;}----------------------------------------------------------------------------------------------------------------------------[后缀数组]最长重复子串分析：任何一个重复子串，必然是某两个后缀的公共前缀。
