后缀数组-_′ⅰ

后缀数组

---

代码

/*
n:代表字符串长度 m:代表字符集大小 
s数组：字符串数组,内容从下标1开始
rk数组:排名数组
c数组：基数排序的数组，下标为待排序的数字，值为该数字出现的次数。排序过程中，我们会对其求前缀和以便计算排名
x数组：是一个中间量数组，意义为得到第一关键字的大小，对于一次排序，下标为代表后缀编号，值为象征对应后缀编号第一关键字大小的值（事实上可以视作排名）
y数组：是一个中间量数组，意义为第二关键字的排名，对于一次排序，下标为排名，值为第二关键字对应的后缀的编号
*/
void get_sa()
{
    //统计该次第一关键字（首字母）的出现次数
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    //计算前缀和
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];	
    //计算第一次排序的sa,此次基数排序,仅区分首字母和后缀编号，首字母小的在前，首字母相同，后缀编号小（后缀长度大）的在前
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    
    for (int k = 1; k <= n; k <<= 1)
    {
        //从21~31都是倍增计算y数组 先进行第二关键字排序
        int num = 0;
        //有一些后缀拆分后的第二关键字为空，这个循环将这些后缀的排名提到最前，以表示空字符的最高优先级
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        /*
        对于满的第二关键字排序，利用某一后缀的后缀也是原串的后缀这一特点,由上一次的sa计算而来.
        考虑那些排名靠前的后缀，如果往前补倍增长度位，那么这个后缀对应的长度前缀就变成了第二关键字
        比如我们有后缀aa和abaa,长度为2,计算abaa的第二关键字的时候，实际上查到的是aa的排名，并且往前补了2位。
        */
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        
        /*
        从36~44是基数排序倍增计算x[] 这是对第一关键字排序 此时求得的x[]含义是旧的排名,是长度为2^k的排名
        */
        for (int i = 1; i <= m; i ++ ) c[i] = 0;	//清空
        //y[i]表示的是第二关键字排名为i的后缀编号  
        //而x[i]拿到的则是第一关键字排序时，后缀编号为i的后缀对应的象征第一关键字大小的值
        //（在初始化过程中，我们将该值设置为首字母的值了，因此，对初始化还有一种理解，即y[i] = i，并没对第二关键字排序）
        //因此x[y[i]]的值反映的是代表第一关键字大小的值
        for (int i = 1; i <= n; i ++ ) c[x[y[i]]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        //对i逆序统计，其用意是：当第一关键字相同的时候，第二关键字排名大的，计算后sa的值也会更大
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        
        //从48~54都是在求新的x[],即求长度为2^(k+1)的排名
        //y已经清空了,把旧的x数组值换到y数组上
        swap(x, y);
        //规定当前排名第一的后缀x值为1,以后的后缀x值不会小于1
        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;
        //当本次排序中已经产生了不小于n种不同的第一关键字的值，排序便没有必要继续下去了，因为已经区分开了这些后缀。
        if (num == n) break;
        //本次排序更新了关键字的种类数，因此要更新m值  更新基数排序的值域
        m = num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

---

后缀数组的相关概念

后缀

后缀：指从某个位置开始到字符串末尾的一个特殊子串。字符串$s$从第$i$个字符开始的后缀被表示为$Suffix(i)$，也可以称之为下标为$i$的后缀。

例如字符串$s=$"$aabaaaab$"，其所有的后缀如下：

• $Suffix(0)=$“$aabaaaab$”
• $Suffix(1)=$“$abaaaab$”
• $Suffix(2)=$“$baaaab$”
• $Suffix(3)=$“$aaaab$”
• $Suffix(4)=$“$aaab$”
• $Suffix(5)=$“$aab$”
• $Suffix(6)=$“$ab$”
• $Suffix(7)=$“$b$”

后缀数组

将所有后缀都从小到大排序之后，将排好序的后缀的下标$i$放入数组中，则该数组就叫做后缀数组（Suffix Array），$SA[num]=i$表示排名为$num$的后缀其下标为$i$

将上面的所有后缀都按字典序排序之后，取其下标$i$，即可得到后缀数组：

• $Suffix(3)=$“$aaaab$”
• $Suffix(4)=$“$aaab$”
• $Suffix(5)=$“$aab$”
• $Suffix(0)=$“$aabaaaab$”
• $Suffix(6)=$“$ab$”
• $Suffix(1)=$“$abaaaab$”
• $Suffix(7)=$“$b$”
• $Suffix(2)=$“$baaaab$”

后缀数组SA[]={3,4,5,0,6,1,7,2}

排名数组

排名数组是指下标为$i$的后缀排序后的名次，即第$i$个后缀排名是啥，$rank[i]=num$表示第$i$个后缀其排名为$num$

下标为3的后缀，排名为1，即$rank[3]=1$；排名第1的后缀，下标为$3$，即$SA[1]=3$。排名数组和后缀数组是互逆的，可以相互转换，并且$rank[SA[l]]=l$，$SA[rank[i]]=i$

用$rk[]$推导$sa[]$：

for(int i=0;i<n;i++)
    sa[rk[i]]=i;
1
2

用$sa[]$推导$rk[]$：

for(int i=0;i<n;i++)
    rk[sa[i]]=i;
1
2

---

后缀数组的构建思路

构建后缀数组有两种方法：$DC3$算法和倍增算法。前者时间复杂度为$O(n)$，后者时间复杂度为$O(nlogn)$。一般来说都是使用倍增算法

采用倍增算法，对字符串从每个下标开始的长度为$2^k$的子串进行排序，得到排名。$k$从0开始，每次都增加1，相当于长度增加了1倍。当$2^k\ge n$时，从每个下标开始的长度为$2^k$的子串都相当于所有后缀。每次子串排序都需要用到上一次子串的排名得到。

图解如下：

设字符串$s$="$aabaaaab$"

（1）将字符串$s$从每个下标开始长度为1的子串进行排名，一般来说都是将该字符的ASCII码作为其排名，但是这里直接将每个字符转成数字$s[i]-$’$a$’+$1$，如下图：

（2）求解长度为$2^1$的子串排名，将上一次$rank$值的第$i$个和第$i+1$个结合，相当于得到长度为$2^1$的子串的每个位置排名，然后排序，即可得到长度为$2^1$的子串排名，如下图：

（3）求解长度为$2^2$的子串排名，将上一次$rank$值的第$i$个和第$i+2$个结合，相当于得到长度为$2^2$的子串的每个位置排名，然后排序，即可得到长度为$2^2$的子串排名，如下图：

（4）求解长度为$2^3$的子串排名，将上一次$rank$值的第$i$个和第$i+4$个结合，相当于得到长度为$2^3$的子串的每个位置排名，然后排序，即可得到长度为$2^3$的子串排名，如下图：

由于此时$2^k=2^3=8$，已经等于了$n=8$，因此，结束。

我们发现第4步和第3步的结果是相同的，实际上，如果在$rank$没有相同值时已经得到了后缀排名，就不需要再继续运算了。这主要是根据字符串比较的规则，如果两个字符串的前面几个字符已经比出了大小关系，那么就不再需要考虑后面字符的比较了。

将排名数组转换成后缀数组，排名第1的下标为3，排名第2的下标为4，排名第3的下标为5，排名第4的下标为0，排名第5的下标为6，排名第6的下标为1，排名第7的下标为7，排名第8的下标为2

因此得到后缀数组SA[]={3,4,5,0,6,1,7,2}

因为是倍增算法，每次比较的字符数都翻倍，因此长度为$n$的字符串最多需要$O(logn)$次排序，采用基数排序，其时间复杂度为$O(n)$，因此进行$n$趟排序后，求解后缀数组总的时间复杂度就是$O(nlogn)$

记sub[i][k]表示$s$从$i$开始长度为$2^k$的子串，$sub[i][k]$其实也就是$s[i],s[i+1],\cdots ,s[i+(1<<k)-1]$，超过$n$的部分都被视为’\0’（ASCII为0，字典序最小的字符，即空字符）

记rank[i][k]表示$sub[i][k]$在长度为$2^k$的所有子串中的排名

记sa[l][k]表示在长度为$2^k$的所有子串中排名第$l$的子串的开始位置

倍增过程：

• step 1：求出长度为$2^0$的子串的字典排序，即求出$sub[1][0]$，$sub[2][0]$，$\cdots$，$sub[n][0]$的字典排序

• step 2：求出长度为$2^1$的子串的字典排序，即求出$sub[1][1]$，$sub[2][1]$，$\cdots$，$sub[n][1]$的字典排序

• $\cdots$

• step k：求出长度为$2^k$的子串的字典排序，即求出$sub[1][k]$，$sub[2][k]$，$\cdots$，$sub[n][k]$的字典排序

• 当子串长度$2^k\ge n$时，子串排序就是后缀排序

现在来思考一下，如何利用$rank[1\cdots n][k]$，求出$rank[1\cdots n][k+1]$呢？

对于两个子串$sub[i][k+1]$和$sub[j][k+1]$，我们可以这么比较：将长度一分为二，先比较前一半，如果前一半能得到结果则结束；否则再接着比较后一半

• 先比较$rank[i][k]$和$rank[j][k]$
• 如果相等，再比较$rank[i+2^k]$和$rank[j+2^k]$
• 那么我们发现，其实我们就是再对二元组$(rank[i][k],rank[i+2^k][k])$进行排序。联想C++中pair二元组可知，先按first比较，如果相等，再按second比较。受此启发，我们可以知道要解决这个问题，需要对第一个关键字和第二个关键字进行排序

从上可以观察到一个性质：想要求出长度为$k+1$的排名，需要用到长度为$k$的排名

如下图所示：

注意到$rank[i][j]$值域是不会超过$n$的正整数（可能会有相同），因此可以使用基数排序。对于一个三位的十进制数，如果使用基数排序，则先排个位，再排十位，最后排百位，即从低位到高位进行排序。联想C++中的pair是$<first,second>$，那么我们可以类比于十进制的基数排序，从右到左分别是从低位到高位，因此对于二元组排序来说，是先排second，再排first，即先排第二关键字，然后再排第一关键字。

---

后缀数组的实现

如何理解下面这段代码呢？

这一段代码其实是处理长度为$2^k=2^0=1$的单个字符的后缀

这里$n$是该字符串$s$的长度，$m=122$

    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
1
2
3

首先来理解第一行代码：

for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
1

x[i]=s[i]表示将$s[i]$这个字符的ASCII值作为这个字符的排名，假设字符串$s$为$adcab$，那么有：

• $x[1]=s[1]=$‘$a$’=97，$c[97]$++，所以$c[97]=1$
• $x[2]=s[2]=$‘$d$’=100，$c[100]$++，所以$c[100]=1$
• $x[3]=s[3]=$‘$c$’=99，$c[99]$++，所以$c[99]=1$
• $x[4]=s[4]=$‘$a$’=97，$c[97]$++，所以$c[97]=2$
• $x[5]=s[5]=$‘$b$’=98，$c[98]$++，所以$c[98]=1$

再来理解第二行代码：

for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
1

这里其实就是类似于求前缀和

• 当$i=97$时，$c[97]=c[i]+c[i-1]=c[97]+c[96]=2+0=2$
• 当$i=98$时，$c[98]=c[i]+c[i-1]=c[98]+c[97]=1+2=3$
• 当$i=99$时，$c[99]=c[i]+c[i-1]=c[99]+c[98]=1+3=4$
• 当$i=100$时，$c[100]=c[i]+c[i-1]=c[100]+c[99]=1+4=5$

最后来理解第三行代码：

for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
1

• 当$i=5$时，$x[5]=9$8，$c[98]=3$，则$sa[3]=5$，然后$c[98]$--，于是$c[98]=2$
• 当$i=4$时，$x[4]=97$，$c[97]=2$，则$sa[2]=4$，然后$c[97]$–，于是$c[97]=1$
• 当$i=3$时，$x[3]=99$，$c[99]=4$，则$sa[4]=3$，然后$c[99]$–，于是$c[99]=3$
• 当$i=2$时，$x[2]=100$，$c[100]=5$，则$sa[5]=2$，然后$c[100]$–，于是$c[100]=4$
• 当$i=1$时，$x[1]=97$，$c[97]=1$，则$sa[1]=1$，然后$c[97]$–，于是$c[97]=0$
• 因此得到长度为$2^k=2^0=1$的子串的后缀数组SA[]={1,4,5,3,2}

图示理解如下：

总结：

for k=1~logn

• 先按第二关键字排序，即按$rank[i+2^k][k]$进行基数排序
• 然后再按第一关键字排序，即按$rank[i][k]$进行基数排序
• 通过上面图片中的栗子可以看出，求出了$rangk[i+2^k][k]$和$rank[i][k]$后，就可以递推得到了$k+1$时的后缀数组Sa[]，即得到$sa[i][k+1]$
• 最后我们又用$sa[i][k+1]$求出了$k+1$时的排名数组$rank[i][k+1]$

如何理解下面这段代码：

        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
1
2
3
4

理解如下：

比如字符串$s$为$aabaaaab$，我们将每个字符都转换成数字，转换规则是$s[i]{-}^{\prime }{a}^{\prime }+1$，求出长度为$k=0,2^k=2^0=1$的子串的排名数组$x[]$（相当于rank[]），进行基数排序，为了放置比较时越界，在末尾用0封装：

接下来求解子串长度为$k=1,2^k=2^1=2$的：

我们对第二关键字进行基数排序，将排序结果存储在y[]中：

从上面我们发现，将上一次的排名x[]前移错位（-k），就可以得到第2关键字的排序结果（下标）y[]

如何理解下面这段代码：

        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[y[i]]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
1
2
3
4

理解如下：

这段代码其实是在对第1关键字进行基数排序，特别是需要注意理解c[x[y[i]]] ++和sa[c[x[y[i]]] -- ] = y[i]是什么意思：

• 当$i=0$时，$y[0]=8$，然后$x[8]=0$，而这个0刚好就是补0的空字符的第1关键字的大小
• 当$i=1$时，$y[1]=7$，然后$x[7]=2$，而这个2刚好就是第1关键字’b’的大小
• 当$i=2$时，$y[2]=0$，然后$x[0]=1$，而这个1刚好就是第1关键字’a’的大小
• 当$i=3$时，$y[3]=$2，然后$x[2]=2$，而这个2刚好就是第1关键字’b’的大小
• 当$i=4$时，$y[4]=3$，然后$x[3]=1$，而这个1刚好就是第1关键字’a’的大小
• …

因此，我们发现：将第2关键字的排序结果y[]转换成排名，正好是第1关键字！由于我们是对第1关键字进行基数排序，因此通过x[y[i]]的转换，就巧妙地利用已经求出来的y[]来得到我们想要的第1关键字x[]。

因此这就解释了c[x[y[i]]] ++

对第1关键字进行基数排序，按第1关键字的排名顺序将x[]中的值$x[i]$作为桶的编号，由上图可知，$x[]$的值域有0、1、2，然后将$y[i]$的值丢入桶中：

• 当$i=0$时，$y[0]=8$，这个8丢入桶中，$x[8]=0$，即$x[y[0]]=0$，这个0作为桶的编号
• 当$i=1$时，$y[1]=7$，这个7丢入桶中，$x[7]=2$，即$x[y[1]]=2$，这个2作为桶的编号
• 当$i=2$时，$y[2]=0$，这个0丢入桶中，$x[0]=1$，即$x[y[2]]=1$，这个1作为桶的编号
• 当$i=3$时，$y[3]=2$，这个2丢入桶中，$x[2]=2$，即$x[y[3]]=2$，这个2作为桶的编号
• 当$i=4$时，$y[4]=3$，这个3丢入桶中，$x[3]=1$，即$x[y[4]]=1$，这个1作为桶的编号
• 当$i=5$时，$y[5]=4$，这4丢入桶中，$x[4]=1$，即$x[y[5]]=1$，这个1作为桶的编号
• 当$i=6$时，$y[6]=5$，这个5丢入桶中，$x[5]=1$，即$x[y[6]]=1$，这个1作为桶的编号
• 当$i=7$时，$y[7]=1$，这个1丢入桶中，$x[1]=1$，即$x[y[7]]=1$，这个1作为桶的编号
• 当$i=8$时，$y[8]=6$，这个6丢入桶中，$x[6]=1$，即$x[y[8]]=1$，这个1作为桶的编号

如下图：

因此这就是解释了sa[c[x[y[i]]] -- ] = y[i]

如何理解这段代码呢？

        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;
        if (num == n) break;
        m = num;
1
2
3
4
5
6

理解如下：

根据$sa[]$和$x[]$数组计算新的排名数组（长度为2的子串排名）。因为要使用旧的x[]数组计算新的x[]数组，由于我们之前已经把$y[i]$都清0了，因此此时的y[]是空的没有用了，因此将$x[]$和$y[]$交换，swap(x,y)，此时的$y[]$数组就是旧的$x[]$数组了，然后现在需要计算新的$x[]$数组

我们初始化x[sa[1]] = 1，因为$sa[1]$表示排名为1的子串所对应的下标位置，既然这个子串它是排名第1，那么它在新的排名中也仍然是第一，因此我们把它初始化为1

下面举个栗子：

设字符串$s$为 $aabaab

当$k=0$时，已经处理完了长度为$2^0$的子串了

然后现在来处理$k=1$，即长度为$2^1$的子串：

接下来理解如何用得到的新的SA[]数组求出下一轮的排名数组tempRA[]，即通过$sa[i][k+1]$求出$rank[i][k+1]$

我们从上往下扫描，即$i=0$扫描到$i=8$，比较当前$i$这一层中的$RA[SA[i]]$、$RA[SA[i]+k]$与上一层$i-1$中的$RA[SA[i]]$、$RA[SA[i]+k]$，如果都相等，则说明它俩都是同一个排名，如果第$i$层的大，则说明第$i$层的排名比上一层$i-1$的排名多1

• 当$i=0$时，$tempRA[0]=0$
• 当$i=1$时，由于$RA[SA[1]]>RA[SA[0]]$，因此，$tempRA[1]=1$
• 当$i=2$时，由于$RA[SA[2]]=RA[SA[1]]$并且$RA[SA[2]+k]=RA[SA[1]+k]$，因此$tempRA[2]=tempRA[1]=1$
• 当$i=3$时，由于$RA[SA[3]]=RA[SA[2]]$并且$RA[SA[3]+k]=RA[SA[2]+k]$，因此$tempRA[3]=tempRA[2]=1$
• 当$i=4$时，由于$RA[SA[4]]=RA[SA[3]]$并且$RA[SA[4]+k]=RA[SA[3]+k]$，因此$tempRA[4]=tempRA[3]=1$
• 当$i=5$时，由于$RA[SA[5]]=RA[SA[4]]$但是$RA[SA[5]+k]>RA[SA[4]+k]$，因此$tempRA[5]=2$
• 当$i=6$时，由于$RA[SA[6]]=RA[SA[5]]$并且$RA[SA[6]+k]=RA[SA[5]+k]$，因此$tempRA[6]=2$
• 当$i=7$时，由于$RA[SA[7]]>RA[SA[6]]$，因此$tempRA[7]=3$
• 当$i=8$时，由于$RA[SA[8]]=RA[SA[7]]$但是$RA[SA[8]+k]>RA[SA[7]+k]$，因此$tempRA[8]=4$

然后再根据$RA[SA[i]]$和$RA[SA[i]+2]$求出新的SA[]：

再从上往下遍历，更新$tempRA[]$

然后当$k=3$时，子串长度为$2^3$，需要用到子串长度为$2^2$，因此我们将当$k=2$时得到的$tempRA[]$作为$k=3$时的第一关键字，比如当$k=3$时为$aabaab，则我们需要用到前面四个

$aab，则这已经在上一层k=2时求出来了，于是直接把上一层k=2的排名直接复制给k=3时的第一关键字就好了：

如下图：

通过上面一顿操作，我们发现，如果当前第$i$层的$y[sa[i]]$等于上一层$i-1$层的$y[sa[i-1]]$，并且当前第$i$层的$y[sa[i]+k]$等于上一层$i-1$层的$y[sa[i-1]+k]$，则说明这俩层的子串的排名都都是相同的，否则第$i$层的排名就比第$i-1$层的排名要高（因为我们已经基础排序了，从小到大了），所以num++即可。当$num=n$时，则说明有$n$个不同的排名，因此就可以退出了。最后$m=num$其实就是优化基数排序的值域。

---

最长公共前缀LCP

最长公共前缀是指两个字符串中长度最大的公共前缀，例如$s_1=$"$abcxd$"，$s_2=$"$abcdef$"，那么$LCP(s_1,s_2)=$"$abc$"，其长度为3。

对于字符串$s=$"$aabaaaab$"，$suffix(sa[i])$表示从第$sa[i]$个字符开始的后缀，其排名为$i$。例如$sa[3]=5$，$suffix(sa[3])=$"$aab$"，表示从第5个字符开始的后缀，其排名为3。

$height$表示排名相邻的两个后缀的最长公共前缀的长度，$height[2]=3$表示排名第2的后缀和排名前一个后缀的最长公共前缀的长度为3。

如下图：

$height[i]$表示$suffix(sa[i])$和$suffix(sa[i-1])$的最长公共前缀的长度。

**性质1：**对于任意两个后缀$suffix(i)、suffix(j)$，如果$rank[i]<rank[j]$，则它们的最长公共前缀的长度为$height[rank[i]+1]，height[rank[i]+2]，\cdots ，height[rank[j]]$的最小值

例如，$suffix(4)=$"$aaab$"，$suffix(1)=$"$abaaab$"，$rank[4]=2$，$rank[1]=6$，它们的最长公共前缀长度为$height[3]$，$height[4]$，$height[5]$，$height[6]$的最小值。

如下图所示：

那么我们该如何求解$height$数组呢？如果两两比较，则时间复杂度为$O(n^2)$；若利用它们之间的关系进行线性递推，则时间复杂度为$O(n)$

定义$h$数组，$h[i]=height[rank[i]]$，其中$h[i]$的含义：第$i$个后缀（下标为$i$开始的后缀）和排名在第$i$个后缀前面的那个后缀的 最长公共前缀

根据$rank[]$和$sa[]$的互逆性，$rank[3]=1$，$h[3]=height[rank[3]]=height[1]=0$；$rank[4]=2$，$h[4]=height[rank[4]]=height[2]=3$。实际上，height[]和h[]只是下标不同而已，前者使用$rank$作为下标，后者使用$sa$作为下标。

如下图所示：

性质2：$h[i]\ge h[i-1]-1$

有了这个性质，我们就可以枚举$i$从1到$n$，枚举以$i$结尾的后缀，先求解出$h[i-1]$，设$k=h[i-1]$，如果$k>0$，则k--，也就是$h[i-1]-1$了，然后得到新的$k$，最后把这个$k$赋值给$h[i]$就好了。我们在求出$h[i-1]-1$的基础上继续计算$h[i]$即可，没有必要再从$1$开始枚举了。

完美图解：

（1）$i=0$

• 先将下标转换为排名，$rank[0]=4$
• 求它的前一名，于是$rank[0]-1=4-1=3$
• 将前一名转换为下标，$sa[3]=5$，因此$j=5$
• 从$k=0$开始比较，如果$s[i+k]==s[j+k]$，那么k++，在比较结束时，$k=3$，那么$height[rank[0]]=height[4]=k=3$

如下图所示

（2）$i=1$

• 先将下标转换为排名，$rank[1]=6$
• 求它的前一名，于是$rank[1]-1=6-1=5$
• 将前一名转换为下标，$sa[5]=6$，因此$j=6$
• 此时$k=3,k\ne 0$，因此从上一次的运算结果$k-1$开始接着比较，其实也就是$k=h[i-1]$，$k-1$就相当于$h[i-1]-1$，所以此时新的$k=2$，因为$s[i+k]\ne s[j+k]$，则$k$不能增加，即此时不能在对比这两个后缀了，因此$height[6]=2$。

如下图所示

（3）继续求解$i=2,3,\cdots ,n$，即可得到所有的height[]

代码：

void get_Height()
{
    //先初始化rk
    for(int i=1;i<=n;i++)
        rk[sa[i]]=i;
    //i从1到n,枚举以下标i开始的后缀
    for(int i=1,k=0;i<=n;i++)
    {
        //这里的k相当于h[i-1] 如果k>0,那么k-1就相当于h[i-1]-1
        if(k)
            k--;
        //根据h[i]的定义可知,现在是在枚举下标i开始的后缀
        //rk[i]-1表示排名在 以下标i开始的后缀 的前面那个后缀的排名
        //那么sa[rk[i]-1]就可以得到 前面那个后缀 的 下标j
        int j=sa[rk[i]-1];
        //依次扫描对比这两个后缀,如果i+k下标不超过n,并且j+k下标不超过n
        //并且扫描到的字符都相等s[i+k]==s[j+k],则让k继续走
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])
            k++;
        //我们知道h[i]=height[rk[i]],而这里的k是更新过后的h[i-1]-1,因此height[rk[i]]=k就相当于
        //h[i]=h[i-1]-1
        height[rk[i]]=k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---