传送门：

思路：非常水的后缀数组，把串复制一遍到后面，后缀排序即可。

#include
    
     #include
     
      #include
      
       const int maxn=200010;using namespace std;int n,t1[maxn],t2[maxn],sa[maxn],rank[maxn],sum[maxn],cnt;char s[maxn];void getsa(){	int *x=t1,*y=t2,m=255,p=0;	for (int i=1;i<=n;i++) sum[x[i]=s[i]]++;	for (int i=1;i<=m;i++) sum[i]+=sum[i-1];	for (int i=n;i;i--) sa[sum[x[i]]--]=i;	for (int j=1;p
       
        <<=1,m=p){		p=0;		for (int i=n-j+1;i<=n;i++) y[++p]=i;		for (int i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;		memset(sum,0,sizeof(sum));		for (int i=1;i<=n;i++) sum[x[y[i]]]++;		for (int i=1;i<=m;i++) sum[i]+=sum[i-1];		for (int i=n;i;i--) sa[sum[x[y[i]]]--]=y[i];		swap(x,y),x[sa[1]]=p=1;		for (int i=2;i<=n;i++){			if (y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]) p++;			x[sa[i]]=p;		}	}	memcpy(rank,x,sizeof(rank));}int main(){	scanf("%s",s+1),n=strlen(s+1);	for (int i=1;i<=n;i++) s[i+n]=s[i];	s[(n=n*2)+1]='\0',getsa(),n/=2;	for (int i=1;i<=n*2;i++) if (sa[i]<=n) putchar(s[sa[i]+n-1]);	puts("");	return 0;}