题意：读入一个长度为 $ n $ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $ 1 $ 到 $ n $。其中\(1\le n \le 10^6\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1e6+5;
const int M=2e5+5;
const int mod=1e9+7;
char s[N];
int n,m,rak[N],tp[N],tax[N],sa[N];
void Qsort(){
for(int i=0;i<=m;++i)tax[i]=0;
for(int i=1;i<=n;++i)++tax[rak[i]];
for(int i=1;i<=m;++i)tax[i]+=tax[i-1];
for(int i=n;i>=1;--i)sa[tax[rak[tp[i]]]--]=tp[i];
}
void SA(){
m=127;
for(int i=1;i<=n;++i)rak[i]=s[i]-'0'+1,tp[i]=i;
Qsort();
int p=0;
for(int w=1;p<n;w<<=1){
p=0;
for(int i=1;i<=w;++i)tp[++p]=n-w+i;
for(int i=1;i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
Qsort();
swap(tp,rak);
rak[sa[1]]=p=1;
for(int i=2;i<=n;++i)
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
m=p;
}
}
int main() {
scanf("%s",s+1);
n=strlen(s+1);
SA();
for(int i=1;i<=n;++i)cout<<sa[i]<<" ";cout<<endl;
return 0;
}