后缀数组

 #include<stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e6+7;
char str[maxn];
int sa[maxn],tp[maxn],rak[maxn],tax[maxn],a[maxn],M,N;
//  sa代表着 排名第i小的下标是什么
//  rak 代表 下标为i的串的排名是什么
//  顾 rak[sa[i]]==i   sa[rak[i]]=i

void qsort(){
    for(int i=0;i<=M;i++) tax[i]=0;
    for(int i=1;i<=N;i++) tax[rak[i]]++;
    for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
    // 这个循环操作相当于把 在原来sa的基础上 再次按照 tp的rank排名 再排序
    for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort(){
    M=127;
    for(int i=1;i<=N;i++)rak[i]=a[i],tp[i]=i;
    qsort();
    for(int w=1,p=1; p<N ; M=p,w<<=1)
    {

        p=0;

        //更新第二关键值
        /**********************************/
        for(int i=N-w+1;i<=N;i++) tp[++p]=i;// 长度越界,第二关键字为0

        for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
        /**********************************/
        qsort();

        // 把 rak里面的数据转移到tp里面
        swap(rak,tp);

        //这个操作等于统计了下次需要的桶的个数
        rak[sa[1]]=p=1;
        for(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;
    }
}
int height[maxn];
//height[i]为LCP(i,i-1)
//LCP(i,j)为suff(sa[i])与suff(sa[j])的最长公共前缀
/*
LCP的性质
LCP(i,j)=LCP(j,i);
LCP(i,i)=len(sa[i])=n-sa[i]+1;
*/
//LCP(rk[i],rk[k+1])=height[rk[i-1]]-1;
int get_height()
{
    int k=0;
    for (int i=1;i<=N;++i) rak[sa[i]]=i;
    for (int i=1;i<=N;++i)
    {
        if (rak[i]==1) continue;//第一名height为0
        if (k) --k;//h[i]>=h[i-1]+1;
        int j=sa[rak[i]-1];
        while (j+k<=N && i+k<=N && a[i+k]==a[j+k]) ++k;
        height[rak[i]]=k;//h[i]=height[rk[i]];
    }
    for (int i=1;i<=N;++i)cout<<height[i]<<endl;
}
int main()
{
    scanf("%s",str);
    N=strlen(str);
    for(int i=1;i<=N;i++)a[i]=str[i-1]-48;
    Ssort();
    for(int i=1;i<=N;i++)
        printf("%d ",sa[i]);
    puts("");
    get_height();
    return 0;
}


ababa
5 3 1 4 2
0 1 3 0 2

 #include<stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e6+7;
char str[maxn];
int sa[maxn],tp[maxn],rak[maxn],tax[maxn],a[maxn],M,N;
//  sa代表着 排名第i小的下标是什么
//  rak 代表 下标为i的串的排名是什么
//  顾 rak[sa[i]]==i   sa[rak[i]]=i

void qsort(){
    for(int i=0;i<=M;i++) tax[i]=0;
    for(int i=1;i<=N;i++) tax[rak[i]]++;
    for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
    // 这个循环操作相当于把 在原来sa的基础上 再次按照 tp的rank排名 再排序
    for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort(){
    M=127;
    for(int i=1;i<=N;i++)rak[i]=a[i],tp[i]=i;
    qsort();
    for(int w=1,p=1; p<N ; M=p,w<<=1)
    {

        p=0;

        //更新第二关键值
        /**********************************/
        for(int i=N-w+1;i<=N;i++) tp[++p]=i;// 长度越界,第二关键字为0

        for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
        /**********************************/
        qsort();

        // 把 rak里面的数据转移到tp里面
        swap(rak,tp);

        //这个操作等于统计了下次需要的桶的个数
        rak[sa[1]]=p=1;
        for(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;
    }
}
int height[maxn];
//height[i]为LCP(i,i-1)
//LCP(i,j)为suff(sa[i])与suff(sa[j])的最长公共前缀
/*
LCP的性质
LCP(i,j)=LCP(j,i);
LCP(i,i)=len(sa[i])=n-sa[i]+1;
*/
//LCP(rk[i],rk[k+1])=height[rk[i-1]]-1;
int get_height()
{
    int k=0;
    for (int i=1;i<=N;++i) rak[sa[i]]=i;
    for (int i=1;i<=N;++i)
    {
        if (rak[i]==1) continue;//第一名height为0
        if (k) --k;//h[i]>=h[i-1]+1;
        int j=sa[rak[i]-1];
        while (j+k<=N && i+k<=N && a[i+k]==a[j+k]) ++k;
        height[rak[i]]=k;//h[i]=height[rk[i]];
    }
    for (int i=1;i<=N;++i)cout<<height[i]<<endl;
}
int main()
{
    scanf("%s",str);
    N=strlen(str);
    for(int i=1;i<=N;i++)a[i]=str[i-1]-48;
    Ssort();
    for(int i=1;i<=N;i++)
        printf("%d ",sa[i]);
    puts("");
    get_height();
    return 0;
}


ababa
5 3 1 4 2
0 1 3 0 2