为啥 sort 能直接过，玄关

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
string s;
int n,sa[N],rk[2][N<<1];
bool tot;
int l;
bool cmp(int x,int y){
	if(rk[!tot][x]==rk[!tot][y]){
		return rk[!tot][min(n+1,x+l)]<rk[!tot][min(n+1,y+l)];
	}
	return rk[!tot][x]<rk[!tot][y];
}
int main(){
	cin>>s;
	n=s.size();
	s=' '+s;
	for(int i=1;i<=n;i++)sa[i]=i,rk[tot][i]=s[i];
	l=1,tot=0;
	while(l<n){
		tot=!tot;
		sort(sa+1,sa+n+1,cmp);
		int p=0;
		for(int i=1;i<=n;i++){
			if(i==1)rk[tot][sa[i]]=++p;
			else if(rk[!tot][sa[i]]==rk[!tot][sa[i-1]]
			&&rk[!tot][min(n+1,sa[i]+l)]==rk[!tot][min(n+1,sa[i-1]+l)])
				rk[tot][sa[i]]=p;
			else rk[tot][sa[i]]=++p;
		}
		l<<=1;
	}
	for(int i=1;i<=n;i++)cout<<sa[i]<<' ';
	cout<<endl;
	return 0;
}