uoj#35 后缀排序（后缀数组模版）

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 using namespace std;
 4 char s[N];
 5 int a[N],c[N],t1[N],t2[N],sa[N],rk[N],ht[N];
 6 int m,n,p;
 7 void calcsa(int n,int m){
 8     int *x=t1,*y=t2,f=0,p=0;
 9     for(int i=1;i<=m;i++)c[i]=0;
10     for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
11     for(int i=1;i<=m;i++)c[i]+=c[i-1];
12     for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
13     for(int i=1;i<=n&&p<=n;i<<=1){p=0;
14         for(int j=n-i+1;j<=n;j++)y[++p]=j;
15         for(int j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;
16         for(int j=1;j<=m;j++)c[j]=0;
17         for(int j=1;j<=n;j++)c[x[y[j]]]++;
18         for(int j=1;j<=m;j++)c[j]+=c[j-1];
19         for(int j=n;j>=1;j--)sa[c[x[y[j]]]--]=y[j];
20         swap(x,y);x[sa[1]]=1;p=2;
21         for(int j=2;j<=n;j++)
22             x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;
23         m=p;
24     }
25     for(int i=1;i<=n;i++)rk[sa[i]]=i;
26     for(int i=1;i<=n;i++){
27         int j=sa[rk[i]-1];
28         if(f)f--;while(a[i+f]==a[j+f])f++;
29         ht[rk[i]]=f;
30     }
31 }
32 int main(){
33     scanf("%s",s);int len=strlen(s);
34     for(int i=0;i<len;i++)a[++n]=s[i]-'a'+1;
35     calcsa(n,100);
36     for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
37     for(int i=2;i<=n;i++)printf("%d ",ht[i]);puts("");
38     return 0;
39 }