1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 #define maxn 100005 8 int n,m,tot,t1[maxn],t2[maxn],Rank[maxn],sa[maxn],hei[maxn],sum[maxn]; 9 char st[maxn]; 10 int main(){ 11 scanf("%s",st+1),n=strlen(st+1); 12 int *x=t1,*y=t2; 13 m=256; 14 for (int i=1;i<=m;i++) sum[i]=0; 15 for (int i=1;i<=n;i++) sum[x[i]=st[i]]++; 16 for (int i=1;i<=m;i++) sum[i]+=sum[i-1]; 17 for (int i=n;i>=1;i--) sa[sum[x[i]]--]=i; 18 for (int len=1,tot=0;tot<n;len<<=1,m=tot){ 19 tot=0; 20 for (int i=n-len+1;i<=n;i++) y[++tot]=i; 21 for (int i=1;i<=n;i++) if (sa[i]>len) y[++tot]=sa[i]-len; 22 for (int i=1;i<=m;i++) sum[i]=0; 23 for (int i=1;i<=n;i++) sum[x[i]]++; 24 for (int i=1;i<=m;i++) sum[i]+=sum[i-1]; 25 for (int i=n;i>=1;i--) sa[sum[x[y[i]]]--]=y[i]; 26 swap(x,y),tot=0; 27 x[sa[1]]=++tot; 28 for (int i=2;i<=n;i++){ 29 if (y[sa[i]]!=y[sa[i-1]]||y[sa[i]+len]!=y[sa[i-1]+len]) ++tot; 30 x[sa[i]]=tot; 31 } 32 } 33 for (int i=1;i<=n;i++) Rank[i]=x[i]; 34 memset(hei,0,sizeof(hei)); 35 for (int i=1,j=0;i<=n;i++){ 36 if (Rank[i]==1) continue; 37 while (st[i+j]==st[sa[Rank[i]-1]+j]) j++; 38 hei[Rank[i]]=j; 39 if (j) j--; 40 } 41 for (int i=1;i<=n;i++) printf("%d ",sa[i]); 42 return 0; 43 }
后缀数组模板。