传送门
我果然是菜啊，调个裸sa竟然调了一个晚上。。
这题就是普通处理环，把原串复制一遍，做一遍sa就行了。
代码：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int Maxn=200005; char s[Maxn]; int n,m=256; int sa[Maxn],tp[Maxn],tax[Maxn],rank[Maxn]; void Rsort() { for(int i=0;i<=m;i++) tax[i]=0; for(int i=1;i<=n;i++) tax[rank[tp[i]]]++; for(int i=1;i<=m;i++) tax[i]+=tax[i-1]; for(int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i]; } int cmp(int *f,int x,int y,int w) { return f[x]==f[y]&&f[x+w]==f[y+w]; } void suffix() { for(int i=1;i<=n;i++) rank[i]=s[i],tp[i]=i; Rsort(); for(int w=1,p=1,i;p<n;w+=w,m=p) { for(p=0,i=n-w+1;i<=n;i++) tp[++p]=i; for(i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w; Rsort(); swap(rank,tp); rank[sa[1]]=p=1; for( i=2;i<=n;i++) rank[sa[i]]=cmp(tp,sa[i],sa[i-1],w)?p:++p; } } int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) s[i+n]=s[i]; n*=2; suffix(); for(int i=1;i<=n;i++) if(sa[i]<=n/2) printf("%c",s[sa[i]+n/2-1]); return 0; }