#include<bits/stdc++.h>
#define N 1000006
using namespace std;
char s[N];
int px[N],cnt[N],id[N],sa[N],rk[N],oldrk[N<<1];
bool cmp(int x,int y,int w){
    return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int m=300;
	for(int i=1;i<=n;i++) cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1]; 
	for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1){
		int p=0;
		for(int i=n-w+1;i<=n;i++) id[++p]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>w) id[++p]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++) cnt[rk[id[i]]]++;
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]--]=id[i];
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;i++)
			rk[sa[i]]=cmp(sa[i],sa[i-1],w)? p:++p;
	}
	for(int i=1;i<=n;i++) printf("%d ",sa[i]);
	return 0;
}

RT，对比 OIwiki 上的代码，感觉没有问题。

但在 luogu 上只能过一个点，求助