后缀数组之精髓——height数组

上期我们介绍了后缀数组中代码最难写的一部分，今天我们来讲解一下后缀数组中最精髓的一部分——height数组的求解。
【进阶】字符串问题一大利器——后缀数组详解
（附上sa数组求法的讲解）

几个共识

和之前一样，为了后文方便讲解，我们先来达成几个共识。

1、height[i]表示后缀sa[i-1]和后缀sa[i]的最长公共前缀。换句话说，height数组表示排名相邻的两个后缀的最长公共前缀。

2、h[i]表达第i个后缀和排名在他之前一位的后缀的最长公共前缀，即

性质及证明

防止证明过程中公式排版出错，这里仍然采用图片的形式讲解

性质及证明

求解height

我们很容易想到一种朴素的暴力算法，直接在每两个排名相邻的后缀之间枚举求解。但是这种算法最坏情况下的复杂度是O(N^2)的，而且完全没有利用后缀数组的性质。

下面，我们来讲解一种时间复杂度为O(N)的巧妙求法。

利用h数组的性质，我们按照排名的顺序来求解height数组。每次先把长度减1后，循环暴力扩展，并且把求出来的h[i]拷贝到height[rank[i]]即可。由于字符串的长度最大为N，最多进行N次减1操作，所以总计算次数是O(N)级别的。

Code

void height_get(int *r,int n) {
//r为字符串原串，n为字符串长度。
//此处的字符串为添加最小元素后的字符串。
    int k=0;
    for (int i=0;i<n;++i)rank[sa[i]]=i;
    for (int i=0;i<n;++i)
    {
        if (k)k--;
        int j=sa[rank[i]-1];
        while (r[i+k]==r[j+k])k++;
        height[rank[i]]=k;
    }
}//求最长公共前缀,利用h[i]>=h[i-1]-1

写在最后

后缀数组算法的重点在于求解sa数组、rank数组和height数组。有了这三个数组，我们就可以在字符串的世界自由玩耍了【滑稽】。

下期，我将为大家带来后缀数组的经典应用。

【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。