被 $O\left(n\log^2n\right)$ 暴力水过去了

评测记录 和代码：

#include<bits/stdc++.h>
const int maxn=1000005;
using namespace std;
int N,sa[maxn],rk[maxn],id[maxn];
bool Vis[maxn];
char S[maxn];
struct my_pair{
	int a,b,id;
	bool operator<(const my_pair&data)const{
		return a<data.a||a==data.a&&b<data.b;
	}
}A[maxn];
int main(){
	scanf("%s",S+1),N=strlen(S+1);
	for(int i=1;i<=N;i++) Vis[S[i]]=1;
	for(int i=0;i<256;i++) id[i]=(i?id[i-1]:0)+Vis[i];
	for(int i=1;i<=N;i++) rk[i]=id[S[i]];
	for(int k=1;k<=N;k<<=1){
		for(int i=1;i<=N;i++){
			A[i].a=rk[i],A[i].id=i;
			A[i].b=i+k>N?0:rk[i+k];
		}
		sort(A+1,A+N+1);int val=1;
		for(int i=1;i<=N;i++){
			if(i>1&&A[i-1]<A[i]) val++;
			rk[A[i].id]=val;
		}
		if(val==N) break;
	} 
	for(int i=1;i<=N;i++) sa[rk[i]]=i;
	for(int i=1;i<=N;i++) printf("%d%c",sa[i],i==N?'\n':' ');
	return 0;
}