卡常版 $O(N\log^2N)$，不建议学。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char st[N];
int sa[N],rk[N*2],lst[N*2],p;
bool cmp(int x,int y){return rk[x]!=rk[y]?rk[x]<rk[y]:rk[x+p]<rk[y+p];}
signed main()
{
	cin>>(st+1);int n=strlen(st+1);
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=st[i];
	for(p=1;p<n;p<<=1)
	{
		sort(sa+1,sa+n+1,cmp);
		for(int i=1;i<=n;i++)lst[i]=rk[i];
		for(int i=1,cnt=0;i<=n;i++)
		{
			if(lst[sa[i]]==lst[sa[i-1]]&&lst[sa[i]+p]==lst[sa[i-1]+p])
				rk[sa[i]]=cnt;
			else rk[sa[i]]=++cnt;
		}
	}
	for(int i=1;i<=n;i++)cout<<sa[i]-1<<' ';
	return 0;	
}