#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int SA[maxn];//排名为i的后缀的起始位置 
int rk[maxn];//第i个后缀的排名 
char s[maxn];
int fir[maxn];//第一关键字
int sec[maxn];//第二关键字 
int cnt[maxn];//基数排序用的桶 
int tep[maxn];
int len;
int up;
void get_SA(){
    //先按长度为1的开始排序fir[]第一关键字 
    for(int i=1;i<=len;i++) fir[i]=s[i];
    for(int i=1;i<=up;i++) cnt[i]=0;
    for(int i=1;i<=len;i++) cnt[fir[i]]++;
    for(int i=1;i<=up;i++) cnt[i]+=cnt[i-1];
    for(int i=len;i>=1;i--) SA[cnt[fir[i]]--]=i;
    int k=1;//从长度为1开始倍增 
    while(k<len){
        int zj=0;
        for(int i=len-k+1;i<=len;i++) sec[++zj]=i;
        for(int i=1;i<=len;i++) if(SA[i]-k>=1) sec[++zj]=SA[i]-k;
        for(int i=1;i<=up;i++) cnt[i]=0;
        for(int i=1;i<=len;i++) cnt[fir[sec[i]]]++;
        for(int i=1;i<=up;i++) cnt[i]+=cnt[i-1];
        for(int i=len;i>=1;i--) SA[cnt[fir[sec[i]]]--]=sec[i];
        swap(fir,tep);
        zj=0;
        fir[SA[1]]=++zj;
        for(int i=2;i<=len;i++){
            if(SA[i]+k<=len&&SA[i-1]+k<=len&&tep[SA[i]]==tep[SA[i-1]]&&tep[SA[i]+k]==tep[SA[i-1]+k]) fir[SA[i]]=zj;
            else fir[SA[i]]=++zj;
        }
        if(zj==len) break;
        up=zj;
        k<<=1;
    }
    for(int i=1;i<=len;i++){
        printf("%d ",SA[i]);
    }
}
int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    up=127;
    get_SA();
    return 0;
} 

先放代码再说