代码

#include<cassert>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<utility>
using std::cin; using std::cout;
#define N_ 1000010
int n;
char s[N_];
int sa[N_];
int cnt[N_],aux[2][N_];
auto *rnk=aux[0],*tmp=aux[1];
int height[N_];
bool cmp(int x,int y,int w){
    //printf("cmp(%d,%d,%d): (%d,%d) v.s. (%d,%d)\n"
    //,x,y,w,rnk[x],rnk[x+w],rnk[y],rnk[y+w]);
    return rnk[x]==rnk[y]&&((x+w<=n?rnk[x+w]:-1)==(y+w<=n?rnk[y+w]:-1));
}
/*
void show(){
    printf("sa: ");
    for(int i=1;i<=n;++i)printf(" %d",sa[i]);
    putchar('\n');
    printf("rnk:");
    for(int i=1;i<=n;++i)printf(" %d",rnk[i]);
    putchar('\n');
}
*/
void suffix_sort(){
    int i=0,j=0,k=0;
    for(i=0;(++i)<=n;)++cnt[s[i]];
    while((++j)^128)cnt[j]+=cnt[j-1];
    while(--i)rnk[i]=cnt[s[i]]--;
    while((++i)<=n)sa[rnk[i]]=i;
    while(--i)rnk[i]=cnt[s[i]]+1;
    i=n+1;
    for(int len=1;(j=n-len)>0;len<<=1){
        k=0;
        while((--i)^j)tmp[++k]=i;
        for(i=0;(++i)<=n;)if(sa[i]>len)tmp[++k]=sa[i]-len;
        while(--i)cnt[i]=0;
        for(++k;--k;)++cnt[rnk[tmp[k]]];
        for(++i;(++i)<=n;)cnt[i]+=cnt[i-1];
        while(--i)sa[cnt[rnk[tmp[i]]]--]=tmp[i];
        for(++k;(++i)^n||(tmp[sa[i]]=k,++i,false);){
            tmp[sa[i]]=(i^n&&cmp(sa[i],sa[i+1],len)?k:k++);
        }
        std::copy(tmp+1,tmp+n+1,rnk+1);
        //std::swap(rnk,tmp);
    }
}
void calc_height(){
    int i,j,k;
    for(i=1,k=0;i<=n;++i){
        if (rnk[i]==1)continue;
        if(k)--k;
        j=sa[rnk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
        height[rnk[i]]=k;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //scanf("%s",s+1);
    cin>>(s+1);
    n=strlen(s+1);
    suffix_sort();
    calc_height();
    for(int i=1;i<=n;++i)cout<<sa[i]<<' ';//printf("%d ",sa[i]);
    cout<<'\n';
    for(int i=2;i<=n;++i)cout<<height[i]<<' ';
    if(n==1)cout<<'\n';
    return 0;
}

评测结果