RT

本蒟蒻先自己yy了一个按照题意的SA

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+50;
char s[257];
int n,c[N<<1],t1[N<<1],t2[N<<1],sa[N<<1];
inline void build_SA(int m)
{
	int *x=t1,*y=t2;
	for(int i=1;i<=m;i++) c[i]=0;
	for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
	for(int i=2;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(int k=1,p=0;k<=n;k<<=1,m=p,p=0)
	{
		for(int i=1;i<=n;i++) y[++p]=(sa[i]>k? sa[i]-k:sa[i]-k+n);
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) ++c[x[i]];
		for(int i=2;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		p=x[sa[1]]=1;
		for(int i=2;i<=n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[(sa[i]+k-1)%n+1]==y[(sa[i-1]+k-1)%n+1]? p:++p);
		if(p>=n) break;
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	build_SA(257);
	for(int i=1;i<=n;i++)
		printf("%c",s[(sa[i]-2+n)%n+1]);
	return 0;
}

然后数次修改都被无情8个RE了

又模仿题解dalao们写了个破坏成链

数次修改仍8个RE

破坏成链：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+50;
char s[257];
int n,c[N],t1[N<<1],t2[N<<1],sa[N];
inline void build_SA(int m)
{
	int *x=t1,*y=t2;
	for(int i=1;i<=m;i++) c[i]=0;
	for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
	for(int i=2;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int p=0;
		for(int i=n;i>n-k;i--) y[++p]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) ++c[x[i]];
		for(int i=2;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		p=x[sa[1]]=1;
		for(int i=2;i<=n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i-1]+k]==y[sa[i]+k]? p:++p);
		if(p>=n) break;
		m=p;
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=n+1;i<=(n<<1);i++)
		s[i]=s[i-n];
	n<<=1;
	build_SA(300);
	for(int i=1;i<=n;i++)
		if(sa[i]<=(n>>1)) printf("%c",s[sa[i]+(n>>1)-1]);
	return 0;
}

求助dalao们指点迷津 QAQ