后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者 DC3 算法实现，这超出了我们的讨论范围。

在本题中，我们希望使用快排、Hash 与二分实现一个简单的 O(nlog²n) 的后缀数组求法。

详细地说，给定一个长度为 n 的字符串 S（下标 0∼n−1），我们可以用整数 k(0≤k<n) 表示字符串 S 的后缀 S(k∼n−1)。

把字符串 S 的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。

额外地，我们考虑排名为 i 的后缀与排名为 i−1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。

我们的任务就是求出 SA 与 Height 这两个数组。

输入格式
输入一个字符串，其长度不超过 30 万。

字符串由小写字母构成。

输出格式
第一行为数组 SA，相邻两个整数用 1 个空格隔开。

第二行为数组 Height，相邻两个整数用 1 个空格隔开，我们规定 Height[1]=0。

输入样例：

ponoiiipoi

输出样例：

9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

参考答案

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int x[N],y[N],c[N],sa[N],rk[N],height[N],wei[30],n,m;
char s[N];

void SA() 
{
    for ( int i=1; i<=n; i++ ) 
        ++c[x[i]=s[i]]; //c是桶,x[i]是第i个元素的第一关键字
    for ( int i=2; i<=m; i++ ) 
        c[i]+=c[i-1];  //做c的前缀和，我们就可以得出每个关键字最多是在第几名
    for ( int i=n; i>=1; i-- ) 
        sa[c[x[i]]--]=i;
    for ( int k=1; k<=n; k<<=1 ) 
    {
        int num=0;
        for ( int i=n-k+1; i<=n; i++ ) 
            y[++num]=i; //y[i]表示第二关键字排名i的数，第一关键字的位置
                        //第n-k+1到第n位是没有第二关键字的 所以排名在最前面
        for ( int i=1; i<=n; i++ ) 
            if ( sa[i]>k ) y[++num]=sa[i]-k;  //排名为i的数 在数组中是否在第k位以后
//如果(sa[i]>k) 那么可作为别人的2nd关键字，就把它1st关键字的位置添加进y,i枚举第二关键字的排名，靠前的先入队
        for ( int i=1; i<=m; i++ ) 
            c[i]=0;
        for ( int i=1; i<=n; i++ ) 
            ++c[x[i]];  //上一次循环已经算出了这次的第一关键字 所以直接加
        for ( int i=2; i<=m; i++ ) 
            c[i]+=c[i-1];   //第一关键字排名为1~i的数个数 
        for ( int i=n; i>=1; i-- ) 
            sa[c[x[y[i]]]--]=y[i],y[i]=0;
//因为y的顺序是按照第二关键字的顺序来排的
//第二关键字靠后的，在同一个第一关键字桶中排名越靠后
//基数排序
        swap(x,y);
        x[sa[1]]=1; num=1;
        for ( int i=2; i<=n; i++ )
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
//因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字
        if ( num==n ) break;
        m=num;
    }
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",sa[i]-1 );
}

void get_height() 
{
    int k=0;
    for ( int i=1; i<=n; i++ ) 
        rk[sa[i]]=i;
    for ( int i=1; i<=n; i++ ) 
    {
        if ( rk[i]==1 ) continue;//第一名height为0
        if ( k ) --k;   //h[i]>=h[i-1]-1;
        int j=sa[rk[i]-1];
        while ( j+k<=n && i+k<=n && s[i+k]==s[j+k] ) ++k;
        height[rk[i]]=k;    //h[i]=height[rk[i]];
    }
    putchar(10);
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",height[i] );
}

int main() 
{
        scanf( "%s",s+1 );
//  gets( s+1 );

    n=strlen( s+1 ); m=122; //n表示原字符串长度，m表示字符个数，ascll('z')=122
    SA();
    get_height();
}