这份代码的倍增是假的，但是可以通过本题。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m=128,sa[N],x[N],cnt[N],y[N],z[N];
char s[N]; 
int main(){
	cin>>(s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)
		x[i]=s[i],cnt[x[i]]++;
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=n;i++)
		sa[cnt[s[i]]]=i,cnt[s[i]]--;
	for(int i=1;(1<<i)<=n;i++){//注意这里
		int tot=0;
		for(int j=n-i+1;j<=n;j++) y[++tot]=j;
		for(int j=1;j<=n;j++)
			if(sa[j]>i)
				y[++tot]=sa[j]-i;
		memset(cnt,0,sizeof(cnt));
		for(int j=1;j<=n;j++)
			cnt[x[j]]++;
		for(int j=1;j<=m;j++) cnt[j]+=cnt[j-1];
		for(int j=tot;j;j--)
			sa[cnt[x[y[j]]]--]=y[j];
		for(int j=1;j<=n;j++) z[j]=x[j];
		m=0;
		for(int j=1;j<=n;j++)
			if(j>1&&z[sa[j]]==z[sa[j-1]]&&z[sa[j]+i]==z[sa[j-1]+i])
				x[sa[j]]=m;
			else x[sa[j]]=++m;
		if(m==n) break;
	}
	for(int i=1;i<=n;i++)
		cout<<sa[i]<<' ';
	cout<<'\n';
	return 0;
}