1 #include <stdio.h> 2 #include <string.h> 3 const int N = 10000; 4 int rank[N],wb[N],count[27],bucket[N],height[N]; 5  6 void build_sa(int *r, int *sa, int n, int m) 7 { 8     int *x=rank,*y=wb,*t,i,k,p; 9     //给所有后缀的第一个字符排序10     for(i=0; i<m; ++i) count[i] = 0;11     for(i=0; i<n; ++i) count[x[i] = r[i]]++;12     for(i=1; i<m; ++i) count[i] += count[i-1];13     for(i=n-1; i>=0; --i) sa[--count[x[i]]] = i;14 15     for(k=1; k<=n; k*=2)16     {17         p = 0;18         //根据sa数组给所有后缀的第二关关键字排序19         for(i=n-k; i<n; ++i) y[p++] = i;//后缀[n-k,n)的第二关键字都是0，所以排前面20         for(i=0; i<n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;//sa[i] 是sa[i]-k的后缀，又因为sa[]是有序的，所以直接遍历就行了21 22         for(i=0; i<n; ++i) bucket[i] = x[y[i]];//基数排序的收集过程23         //然后基数排序第一关键字24         for(i=0; i<m; ++i) count[i] = 0;25         for(i=0; i<n; ++i) count[bucket[i]] ++;26         for(i=1; i<m; ++i) count[i] += count[i-1];27         for(i=n-1; i>=0; --i) sa[--count[bucket[i]]] = y[i];28         t = x; x = y; y = t;29         p = 1; x[sa[0]] = 0;30         for(i=1; i<n; ++i)//比较第一和第二关键字，要么相等，要么不等，如果相等，则与后缀sa[i-1]的rank值相等，否则，则比sa[i-1]的rank值大31             x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k] ? p-1:p++;32         if(p>=n) break;33         m = p;34     }35 }36 37 void getHeight(int *r, int *sa,int n)38 {39     //h[i]=height[rank[i]] 即h[i]表示后缀i和排在后缀i前一名的后缀的相似度， h[i] >= h[i-1]-140     //按照h[1],h[2],h[3]....的顺序递推计算41     int i,j,k=0;42     for(i=0; i<n; height[rank[i++]]=k)43     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);44     //j=sa[rank[i]-1] 即获取排在i前面一名的后缀下标，45 }46 int main()47 {48     int n,i,sa[N],r[N];49     char str[N];50     scanf("%s",str);51     n = strlen(str);52     for(i=0; i<n; ++i) r[i] = str[i] - ‘a‘ + 1;53     r[n++] = 0;54     build_sa(r,sa,n,27);55     for(i=0; i<n; ++i)56         printf("rank[%d]=%d\n",i,rank[i]);57     puts("");58     for(i=0; i<n; ++i)59         printf("sa[%d]=%d\n",i,sa[i]);60     puts("");61     getHeight(r,sa,n-1);62     for(i=1; i<n; ++i)63         printf("height[%d]=%d\n",i,height[i]);64     return 0;65 }