代码

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

using namespace std;

const int N=1000010;

char s[N];
int n,w,sa[N],rk[N<<1],oldrk[N]; //为了防止访问rk[i+w]导致数组越界，开两倍数组。当然也可以在访问前判断是否越界，但直接开两倍数组方便一些。

int main()
{
    int i,p;
    
    scanf("%s",s+1);
    n=strlen(s+1);
    for (i=1;i<=n;++i) rk[i]=s[i];
    
    for (w=1;w<n;++w)
    {
        for (i=1;i<=n;++i) sa[i]=i;
        sort(sa+1,sa+n+1,[](int x,int y){return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];}); //这里用到了lambda表达式
        memcpy(oldrk,rk,sizeof(oldrk)); //由于计算rk的时候原来的rk会被覆盖，要先复制一份
        for (p=0,i=1;i<=n;++i) rk[sa[i]]=oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]?p:++p; //若两个子串相同，它们对应的rk也需要相同，所以要去重
    }
    
    for (i=1;i<=n;++i) printf("%d ",sa[i]);
    
	return 0;
}

评测结果