题目大意

给定一个长度为$ n$ 的字符串$S$（下标 $0\to n-1$ ），我们可以用整数 $k(0≤k<n)$ 表示字符串 $S$ 的后缀 $S(k~n-1)$ 。

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

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

求出 $SA$与 $Height$ 这两个数组。

思路

后缀数组的模板。

简单来说，就是给你一个字符串，让你对他的n个后缀按字典序进行排序

sa[i] 代表排名为i的后缀的第一个字母在原串中出现的位置，rk[i] 代表从i位置开始的后缀的排名

x[i] 代表后缀i的第一关键字的排名，y[i] 代表第二关键字排名为i的，在以第一关键字排序的排名

c[i] 为基数排序用的桶

正常求后缀排名是 $O(n^2)$ 的

我们通过倍增来将其优化为 $O(nlogn)$

abdae 的后缀为： e ae dae bdae abdae

设通过一轮基数排序成功比较出了第一个字母 $O(n)$ ，

可以发现，每个后缀的第二个字母就是下一个后缀的第一个字母，而第一个字母已经求出，那么就优化了复杂度。

代码

#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();
}