代码

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

using namespace std;

const int N=100010;

char s[N];
int n,w,sa[N],rk[N<<1],oldrk[N],ht[N];

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也需要相同，所以要去重
    }

int k=0;
for (i=1;i<=n;++i)
{
    if (k) --k;
    while (s[i+k]==s[sa[rk[i]-1]+k]) ++k;
    ht[rk[i]]=k;
}
    
    for (i=1;i<=n;++i) printf("%d ",sa[i]);
for (i=2;i<=n;++i) printf("%d ",ht[i]);
    
	return 0;
}

评测结果