rt，$O(n\log^2 n)$ 做法 + O2 跑得飞快。

代码：

#include <bits/stdc++.h>
using namespace std;

string str;
const int N = 1e6+5;
int n,sa[N<<1],rk[N<<1],tmp[N<<1],w,m;

inline bool cmp(int i,int j){
	return rk[i]==rk[j]?(rk[i+w]<rk[j+w]):(rk[i]<rk[j]);
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>str;
	n=str.length();str=" "+str;
	for(int i=1;i<=n;i++) sa[i]=i,rk[i]=str[i];
	for(w=1;w<n;w<<=1){
		stable_sort(sa+1,sa+n+1,cmp);
		memcpy(tmp,rk,sizeof(rk));
		m=0;
		for(int i=1;i<=n;i++){
			if(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+w]==tmp[sa[i-1]+w]) rk[sa[i]]=m;
			else rk[sa[i]]=(++m);
		}
	}
	for(int i=1;i<=n;i++) cout<<sa[i]<<' ';
	return 0;
} 

Record