题目
题解

#include<bits/stdc++.h>
using namespace std;
const int N=1000002;
int rak[N],tp[N],sa[N],n,i,M,tax[N];
char s[N];
void Qsort(){
    memset(tax,0,(M+1)<<2);
    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;i--) sa[tax[rak[tp[i]]]--]=tp[i];
}
void Ssort(){
    M=127;
    for (int i=1;i<=n;i++) rak[i]=s[i],tp[i]=i;
    Qsort();
    for (int w=1,p=1;p<n;M=p,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();
        memcpy(tp,rak,(n+1)<<2);
        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;
    }
    for (int i=1;i<=n;i++) printf("%d ",sa[i]);
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    Ssort();
}