RT,我复杂度假了还是常数太大

提交记录

#pragma Gcc optimize(0)
#pragma Gcc optimize(1)
#pragma Gcc optimize(2)
#pragma Gcc optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
int b[maxn],x[maxn*2],y[maxn*2],sa[maxn];
char s[maxn];
int n,m;
void build_sa()
{
	m=128;
	for(int i=0;i<n;i++)b[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)b[i]+=b[i-1];
	for(int i=n-1;i>=0;i--)sa[--b[x[i]]]=i;
	for(int k=1;k<n;k<<=1)
	{
		int num=0;
		for(int i=n-k;i<n;i++)y[num++]=i;
		for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
		for(int i=0;i<=m;i++)b[i]=0;
		for(int i=0;i<n;i++)b[x[y[i]]]++;
		for(int i=1;i<=m;i++)b[i]+=b[i-1];
		for(int i=n-1;i>=0;i--)sa[--b[x[y[i]]]]=y[i],y[i]=0;
		swap(x,y);num=0;
		x[sa[0]]=0;
		for(int i=1;i<n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n)break;
		m=num;
	}
}
int main()
{
	gets(s);
	n=strlen(s);
	build_sa();
	for(int i=0;i<n;i++)
	printf("%d ",sa[i]+1);
	return 0;
}