奇奇怪怪的优化，可以秒降时间复杂度：

#include<bits/stdc++.h>
using namespace std;
int n,t[1000010],in[1000010],ed[1000010];
char c[1000010];
bool cmp(int a,int b){
	if(in[a]==in[b]){
		int mins=ed[in[a]]-max(a,b);
		a+=mins;
		b+=mins;
	}
	while(a<n&&b<n&&c[a]==c[b]){a++;b++;}
	if(a>=n) return 1;
	if(b>=n) return 0;
	return c[a]<c[b]; 
}
int main(){
	scanf("%s",c);
	n=strlen(c);
	int tot=1;
	in[0]=1;
	for(int i=1;i<n;i++){
		if(c[i]!=c[i-1]){
			ed[tot]=i-1;
			tot++;
		}
		in[i]=tot;
	}
	ed[tot]=n-1;
	for(int i=0;i<n;i++) t[i]=i;
	sort(t,t+n,cmp);
	for(int i=0;i<n;i++) printf("%d ",t[i]+1);
	return 0;
}