后缀数组 height 数组计算与证明 - (sunznx) 振翅飞翔
20 September 2019

几年前写的一篇 后缀树 的文章,本文算是填坑之一。

网上有很多关于后缀数组的介绍,每提到这个话题,都会伴随着 height 数组的求解,以及一个不等式 height[i]>=height[i-1]-1 ,证明这个不等式需要一些数学技巧,本文希望用大白话来证明这个不等式,帮助大家闭着眼睛算出 height 数组,而不是死记硬背。

height 数组的定义:

height 数组就是排序后的两个相邻后缀的最长公共前缀长度是多少

例如字符串 aabaab 有如下后缀:

0 aabaab
1 abaab
2 baab
3 aab
4 ab
5 b

可以求出 SA 数组,rank 数组分别如下

SA[0] = "aab"    = 3   rank[0] = rank["aabaab"] = 1
SA[1] = "aabaab" = 0   rank[1] = rank["abaab"]  = 3
SA[2] = "ab"     = 4   rank[2] = rank["baab"]   = 5
SA[3] = "abaab"  = 1   rank[3] = rank["aab"]    = 0
SA[4] = "b"      = 5   rank[4] = rank["ab"]     = 2
SA[5] = "baab"   = 2   rank[5] = rank["b"]      = 4

根据上面生成的 SA 数组我们可以计算出 height 数组:

height[0] = height["aab"]    = 0
height[1] = height["aabaab"] = 3     # aabaab 和 aab 的公共前缀为 aab
height[2] = height["ab"]     = 1     # ab 和 aabaab  的公共前缀为 a
height[3] = height["abaab"]  = 2     # abaab 和 ab   的公共前缀为 ab
height[4] = height["b"]      = 0     # b 和 abaab    没有公共前缀
height[5] = height["baab"]   = 1     # baab 和 b     的公共前缀为 b

上面的算法用 C 语言实现如下:

for (int i = 0; i < n; i++) {
    height[i] = 0;

    if (i == 0) {
        continue;
    }

    int idx1 = SA[i-1];
    int idx2 = SA[i];

    while (idx1 < n && idx2 < n && str[idx1] == str[idx2]) {
        height[i]++;
        idx1++;
        idx2++;
    }
}

更快的计算出 height 数组:
在我们计算出 height[1]height["aabaab"] 为 3 的时候。因为 height[1]=3 这也就意味着 aabaab 的前一个后缀字符串是 aab...开头的 ,不然 height 长度不会为 3,设这个后缀字符串为 S1
现在我们要计算 height[2]height["abaab"] 的时候,这时候 abaab 的前一个后缀字符串 “最惨的情况” 下应该是 S1 去掉第一个字符串,即 ab...开头的 ,可以推出 height[2] 至少是 2

 1: int k;
 2: for (int i = 0; i < n; i++) {
 3:     int r = rank[i];
 4: 
 5:     if (r == 0) {
 6:         height[r] = 0;
 7:         continue;
 8:     }
 9: 
10:     int j = SA[r-1];
11: 
12:     if (i == 0) {
13:         k = 0;
14:     } else {
15:         k = max(height[rank[i-1]] - 1, 0);   // k 最小为 0
16:     }
17:     while (i+k < n && j+k < n && str[i+k] == str[j+k]) {
18:         k++;
19:     }
20:     height[r] = k;
21: }