环的问题，经典方法倍长串，求出后缀数组，扫一次sa，如果sa[i]小于等于n，那么就输出这个字符串结尾的位置（即s[sa[i]+n-1]）。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4e5+10;
char s[maxn];
int rk[maxn],sa[maxn],sum[maxn],X[maxn];
void SA(char s[],int len) {
for (int i=1;i<=len;++i) ++sum[rk[i]=s[i]];
for (int i=1;i<=300;++i) sum[i]+=sum[i-1];
for (int i=len;i>0;--i) sa[sum[rk[i]]--]=i;
int p=rk[sa[1]]=1;
for (int i=2;i<=len;++i) rk[sa[i]]=(s[sa[i]]==s[sa[i-1]]?p:++p);
for (int j=1;p<len;j<<=1) {
p=0,memset(sum,0,(sizeof sum[0])*(len+1));
for (int i=len-j+1;i<=len;++i) X[++p]=i;
for (int i=1;i<=len;++i) if (sa[i]>j) X[++p]=sa[i]-j;
for (int i=1;i<=len;++i) ++sum[rk[X[i]]];
for (int i=1;i<=len;++i) sum[i]+=sum[i-1];
for (int i=len;i>0;--i) sa[sum[rk[X[i]]]--]=X[i];
memcpy(X,rk,(sizeof rk[0])*(len+1));
p=rk[sa[1]]=1;
for (int i=2;i<=len;++i) rk[sa[i]]=(X[sa[i]]==X[sa[i-1]] && X[sa[i]+j]==X[sa[i-1]+j]?p:++p);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
scanf("%s",s+1);
int n=strlen(s+1),m=n<<1;
for (int i=1;i<=n;++i) s[i+n]=s[i];
SA(s,m);
for (int i=1;i<=m;++i) if (sa[i]<=n) putchar(s[sa[i]+n-1]);
puts("");
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/6816892.html
