rt

就是代码没有使用计数排序。

vector 不应该是动态开空间的吗。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1;

char s[N];

int n,sa[N<<1],rk[N<<1],rk2[N<<1];
vector<int> t1[N],t2[N];
bool cmp(int x,int y) {return s[x]<s[y];}

int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	for(int i=1;i<=n;++i) sa[i]=i;
	sort(sa+1,sa+n+1,cmp);
	for(int i=1,tot=0;i<=n;++i)
	{
		if(i>1 && s[sa[i-1]]==s[sa[i]]) rk[sa[i]]=tot;
		else rk[sa[i]]=++tot;
	}
	for(int len=1;len<=n;len<<=1)
	{
		int r=0;
		for(int i=1;i<=n;++i)
		{
			t2[rk[i+len]].push_back(i);
			r=max(r,rk[i+len]);
		}
		for(int i=0;i<=r;++i)
		{
			for(int x : t2[i])
				t1[rk[x]].push_back(x);
			t2[i].clear();
		}
		int bj=0;
		for(int i=1,tot=0; i<=n && !t1[i].empty(); ++i)
		{
			int pre=t1[i][0];
			rk2[pre]=++tot;
			for(int x : t1[i])
			{
				if(x==pre) continue;
				if(rk[pre+len]==rk[x+len]) bj=1, rk2[x]=tot;
				else rk2[x]=++tot;
				pre=x;
			}
			t1[i].clear();
		}
		memcpy(rk,rk2,sizeof rk2);
		if(!bj) break;
	}
	for(int i=1;i<=n;++i) sa[rk[i]]=i;
	for(int i=1;i<=n;++i) printf("%d ",sa[i]);
}