代码

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

using namespace std;

const int N=100010;

char s[N];
int n,sa[N],sa2[N<<1],rk[N<<1],px[N],cnt[N],height[N];

int main()
{
    int i,j,k,w,p,m=300;
    
    scanf("%s",s+1);
    n=strlen(s+1);
    
    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,m=p)
    {
        memset(cnt,0,sizeof(cnt));
        for (p=0,i=n;i>n-w;--i) sa2[++p]=i;
        for (i=1;i<=n;++i) if (sa[i]>w) sa2[++p]=sa[i]-w;
        for (i=1;i<=n;++i) ++cnt[px[i]=rk[sa2[i]]];
        for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for (i=n;i>=1;--i) sa[cnt[px[i]]--]=sa2[i];
        swap(sa2,rk);
        for (p=0,i=1;i<=n;++i) rk[sa[i]]=sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+w]==sa2[sa[i-1]+w]?p:++p;
    }
    
    for (i=1;i<=n;++i) printf("%d ",sa[i]);
    puts("");
    
    for (i=1,k=0;i<=n;++i)
    {
        if (k) --k;
        while (s[sa[rk[i]-1]+k]==s[i+k]) ++k;
        height[rk[i]]=k;
    }
    
    for (i=2;i<=n;++i) printf("%d ",height[i]);
    
    return 0;
}

评测结果