分析

rk[]（第一关键字）第i位的排名,sa是排名为i的位置,tp[]是第二关键字辅助用的，tax[]是桶数组

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
char str[N];
int sa[N],rk[N],tp[N],tax[N];
int n,m,height[N];
int getr(char c)    //得到该字符的排名  (1~10:'0'~'9',11~36:'A'~'Z',37~62:'a'~'z')
{
    if(c>='0' && c<='9') return c-'0'+1;    
    else if(c>='A' && c<='Z') return c-'A'+11;
    else return c-'a'+37;
}
void Rsort()    //进行基数排序
{
    for(int i=0;i<=m;i++) tax[i]=0;     //初始化桶数组

    for(int i=1;i<=n;i++) tax[rk[tp[i]]]++; //每一个出现的第一关键字++

    for(int i=1;i<=m;i++) tax[i]+=tax[i-1];   //前缀和求出tax[]中i现在代表这个数至多能排第几位
    for(int i=n;i>=1;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}
void Suffix()   //求后缀数组sa[]
{
    for(int i=1;i<=n;i++) rk[i]=getr(str[i]),tp[i]=i;   //刚开始求每个字符排名,第二关键字为其当前位置i
    Rsort();

    for(int k=1;k<=n;k<<=1)
    {
        int num=0;
        for(int i=n-k+1;i<=n;i++) tp[++num]=i; //从n-k+1开始，到n的位置的第二关键字都为0，所以先入数组

        //因为sa是排好序的，当sa[i]这个位置大于k时,就把第二关键字的值赋为sa[i]-k
        for(int i=1;i<=n;i++)   
            if(sa[i]>k)
                tp[++num]=sa[i]-k;

        Rsort();
        swap(rk,tp);
        rk[sa[1]]=1;    //rk[sa[1]]本身为1
        num=1;   //用num来更新排名
         //比较第一和第二关键字是否相同,相同，则当前等级为num,否则为++num
        for(int i=2;i<=n;i++)
            rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num;

        if(num==n) break;

        m=num;
    }
    for(int i=1;i<=n;i++) printf("%d ",sa[i]-1);
}
void getH()     //求height[]
{
    int k=0;
    for(int i=1;i<=n;i++) //sa[]已经排好序，此时要初始化rk[]
        rk[sa[i]]=i;

    for(int i=1;i<=n;i++) 
    {
        if(rk[i]==1) continue; //rk[i]为1,说明是第一个,无前缀
        if(k) --k;   
        int j=sa[rk[i]-1];
        while(j+k<=n && i+k<=n && str[i+k]==str[j+k]) ++k;  //只要二者子串相同，就让k++
        height[rk[i]]=k;    //将相同的子串长度k赋给height[]
    }
    for (int i=1;i<=n;i++) 
        printf( "%d ",height[i]);
}
int main()
{
    scanf("%s",str+1);
    n=strlen(str+1);
    m=63;
    Suffix();
    puts("");

    getH();
    return 0;
}