代码来自 算法竞赛入门经典。
#include <cmath> #include <ctime> #include <iostream> #include <string> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <map> #include <set> #include <algorithm> #include <cctype> #include <stack> #include <deque> using namespace std; typedef long long LL; #define EPS 10e-9 #define INF 0x3f3f3f3f #define REP(i,n) for(int i=0; i<(n); i++) const int maxn = 10000; char s[maxn]; int sa[maxn],t[maxn],t2[maxn],c[maxn],n; void build_sa(int m){ int i,*x=t,*y=t2; //基数排序 for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[i]=s[i]-'a' ]++; for(int i=1;i<m;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[ --c[x[i] ] ]=i; for(int k=1;k<=n;k<<=1){ int p=0; //直接利用sa数组排序第二关键字 for(int i=n-k;i<n;i++) y[p++]=i; for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; //基数排序第一关键字 for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[y[i] ] ]++; for(int i=0;i<m;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[--c[x[y[i]] ]]=y[i]; //根据sa和y数组计算新的x数组 swap(x,y); p=1; x[ sa[0] ]=0; for(int i=1;i<n;i++) x[ sa[i] ]=y[ sa[i-1] ]==y[sa[i]]&&y[sa[i-1]+k ]==y[sa[i]+k ]?p-1:p++; if(p>=n) break; m=p; } } int main(){ scanf("%s",s); n=strlen(s); build_sa(26); for(int i=0;i<n;i++) printf("%d ",sa[i]); return 0; }