两篇论文： 　　

贴两模版：

DA：

/*	*后缀数组，倍增算法实现，复杂度O(nlogn)	*sa[i]: 第i小的后缀是在字符串位置，即后缀sa[i]	*rank[i]: 后追i在sa数组下标，即第rank[i]小	*height[i]: LCP (suffix (sa[i-1], sa[i]))*/int sa[N], rank[N], height[N];int ws[N], wa[N], wb[N];bool cmp(int *r, int a, int b, int l) {    return (r[a] == r[b] && r[a+l] == r[b+l]);}//r数组为读入的字符串，m = max (r[i]) + 1，一般字符128足够了//n为strlen (s) + 1，加上最后一个'\0'void DA(char *r, int n, int m = 128) {    int i, j, p, *x = wa, *y = wb;    for (i=0; i
     
      =0; --i) sa[--ws[x[i]]] = i;    for (j=1, p=1; p
      
       = j) y[p++] = sa[i] - j;        for (i=0; i
       
        =0; --i) sa[--ws[x[y[i]]]] = y[i];        std::swap (x, y);        for (p = 1, x[sa[0]] = 0, i=1; i
        
          r) swap (l, r); l++;*/
        
       
      
     

DC3：

/*    *后缀数组，DC3算法实现，复杂度O(n)*/int wa[N],wb[N],wv[N],ws[N];int rank[N],height[N];   int sa[N],r[N];int c0(int *y,int a,int b) {    return y[a]==y[b]&&y[a+1]==y[b+1]&&y[a+2]==y[b+2];}int c12(int k,int *y,int a,int b) {    if(k==2) return y[a]
     
      =0;i--) b[--ws[wv[i]]]=a[i];}void DC3(int *r,int *sa,int n,int m) {    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;    r[n]=r[n+1]=0;    for(i=0;i