代码

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
char s[N];
int n,m;
int rak[N],tp[N],sa[N],tax[N],height[N];
inline void Qsort()
{
    for(register int i=1;i<=m;++i)
        tax[i]=0;
    for(register int i=1;i<=n;++i)
        ++tax[rak[i]];
    for(register int i=1;i<=m;++i)
        tax[i]+=tax[i-1];
    for(register int i=n;i>=1;--i)
        sa[tax[rak[tp[i]]]--]=tp[i];
}
inline void suffixsort()
{
    m=80;
    for(register int i=1;i<=n;++i)
        rak[i]=s[i]-'0',tp[i]=i;
    Qsort();
    for(register int w=1,p=0;p<n;m=p,w<<=1)
    {
        p=0;
        for(register int i=1;i<=w;++i)
            tp[++p]=n-w+i;
        for(register int i=1;i<=n;++i)
            if(sa[i]>w)
                tp[++p]=sa[i]-w;
        Qsort();
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(register int i=2;i<=n;++i)
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
    for(register int i=1;i<=n;++i)
        write(sa[i]),putchar(' ');
}
inline void getheight()
{
    int k=0;
    for(register int i=1;i<=n;++i)
    {
        if(k)
            --k;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])
            ++k;
        height[rak[i]]=k;
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    suffixsort();
    puts("");
    for(register int i=2;i<=n;++i)
         write(height[i]),putchar(' ');
    return 0;
}

评测结果