RT，WA+TLE，对拍发现有的数据会有两个相邻的数输出是反的（例如正确答案21 57输出57 21），调不出来了，谁知道什么原因，思路不对还是实现问题

我自己写的代码，和书上的不太一样，思路是先求rank数组再求sa数组，应该比较好理解

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
char s[maxn];
int x[maxn*2],y[maxn*2],a[maxn],b[maxn],sa[maxn],r[maxn],rk[maxn*2];
int n;
void build_sa()
{
	for(int i=1;i<=n;i++)b[s[i]]++;
	for(int i=1;i<=maxn;i++)b[i]+=b[i-1];
	for(int i=1;i<=n;i++)rk[i]=b[s[i]];
	for(int k=1;k<=n;k<<=1){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++)x[i]=rk[i],y[i]=rk[i+k];
		for(int i=1;i<=n;i++)b[y[i]]++;
		for(int i=1;i<=maxn;i++)b[i]+=b[i-1];
		for(int i=1;i<=n;i++)r[b[y[i]]--]=i;
		for(int i=1;i<=n;i++)a[x[i]]++;
		for(int i=1;i<maxn;i++)a[i]+=a[i-1];
		for(int i=n;i>0;i--)rk[r[i]]=a[x[r[i]]]--;
	}
	for(int i=1;i<=n;i++)
	sa[rk[i]]=i;
}
int main()
{
	s[0]=' ';//个人习惯从1开始
	gets(s+1); 
	n=strlen(s)-1;
	build_sa();
	for(int i=1;i<=n;i++)
	printf("%d ",sa[i]);
	return 0;
}