$O(n\log^2 n)$ 写法，WA on T11

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int sa[N];
string s;
struct node{
	int x,y,p,k;
}as[N];
inline bool cmp(node a,node b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>s;int n=s.size();s=" "+s;
	for(int i=1;i<=n;i++)as[i].x=int(s[i]),as[i].p=i;
	int cnt=0;
	sort(as+1,as+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(as[i].x==as[i-1].x&&as[i].y==as[i-1].y)as[as[i].p].k=cnt;
		else as[as[i].p].k=++cnt;
	}
	for(int j=1;(1<<j)<=n;j++){
//		for(int i=1;i<=n;i++)cout<<as[i].k<<' ';
//		cout<<'\n';
		for(int i=1;i<=n;i++)as[i].x=as[i].k,as[i].p=i;
		for(int i=1;i+(1<<(j-1))<=n;i++)as[i].y=as[i+(1<<(j-1))].k;
		for(int i=n-(1<<(j-1))+1;i<=n;i++)as[i].y=0;
		sort(as+1,as+n+1,cmp);
		cnt=0;
		for(int i=1;i<=n;i++){
			if(as[i].x==as[i-1].x&&as[i].y==as[i-1].y)as[as[i].p].k=cnt;
			else as[as[i].p].k=++cnt;
		}
	}
	for(int i=1;i<=n;i++)cout<<as[i].p<<' ';
	return 0;
}

%%%%%%%%%