代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1000010;

char s[N];
int n,sa[N],rk[N<<1],id[N<<1],px[N],cnt[N]; //px[i]=rk[id[i]]（用于排序的数组所以叫px）

int main()
{
    int i,m,p,w;
    
    scanf("%s",s+1);
    n=strlen(s+1);
    m=max(n,300);
    for (i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for (i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
    
    for (w=1;w<n;w<<=1)
    {
        for (p=0,i=n;i>n-w;--i) id[++p]=i;
        for (i=1;i<=n;++i) if (sa[i]>w) id[++p]=sa[i]-w;
        memset(cnt,0,sizeof(cnt));
        for (i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
        for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for (i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
        swap(rk,id);
        for (p=0,i=1;i<=n;++i) rk[sa[i]]=id[sa[i]]==id[sa[i-1]]&&id[sa[i]+w]==id[sa[i-1]+w]?p:++p; //注意这里的id相当于原来的oldrk
    }
    
    for (i=1;i<=n;++i) printf("%d ",sa[i]);
    
    return 0;
}

评测结果