构造后缀数组
我们会得到两个数组 \(sa_i\) 表示排名为 \(i\) 的后缀是哪一个,\(rk_i\) 表示后缀 \(i\) 的排名。
这里只讲倍增做法。
原理非常简单,如下图:
实现需要一个对两位关键字进行排序的基数排序,设 \(y_i\) 表示按照第二维关键字排序,排名为 \(i\) 的是哪一个位置。设 \(rk_i\) 表示第 \(i\) 个位置,第一维关键字排序,排名是多少。
我们按照 \(i\) 从小到大把 \(rk_{y_i}\) 加入我们的桶中(我们用桶排来实现),对桶做前缀和之后,从大到小枚举 \(n\),按照 \(rk_{y_i}\) 来重新计算每个位置的排名。
这样做正确性显然,考虑如果两个位置第二维关键字排名不同,而第一维相同,那么排名越大的会先被枚举到,导致排名变大。如果第一维就不同,那么第一维更优的显然会排名更小。
所以就可以简单构造了,具体代码请到代码仓库。
求 height
LCP 的定义是最长公共前缀,以下用 \(LCP(i,j)\) 表示编号为 \(i\) 的后缀和编号为 \(j\) 的后缀的 LCP,我们令 \(Height_i=LCP(sa_i,sa_{i-1})\),而 \(Height_1\) 可以视作 \(0\)。我们考虑如何求 \(Height\) 数组。
- 引理:\(Height_{rk_i}\ge Height_{rk_{i-1}}-1\)。
证明:如果 \(Height_{rk_{i-1}-1}\) 小于等于 \(1\),那么上面这个式子显然成立,这是因为 \(Height_i\ge 0\)。
如果 \(Height_{rk_{i-1}-1}>1\),我们考虑设后缀 \(i-1\) 为 \(aAD\),那么后缀 \(i\) 就是 \(AD\),其中 \(A\) 是一个长度为 \(Height_{rk_{i-1}}-1\) 的字符串,由于 \(Height\) 数组的定义,我们考虑后缀 \(sa_{rk_{i-1}-1}\) 这个字符串一定是 \(aAB\) 的形式,所以 \(sa_{rk_{i-1}-1}+1\) 这个后缀一定是 \(AB\) 的形式,所以这个后缀一定排在后缀 \(i\) 的前面,所以我们可以知道 \(Height_{rk_i-1}\) 一定包含字符串 \(A\),所以结论成立。
我们利用上面这个东西就可以 \(O(n)\) 的来求 \(Height\) 数组了。
有一个结论是 \(LCP(sa_i,sa_j)=\min_{i+1\le k\le j}Height_k\),这个可以感性理解一下,如果 \(Height\) 一直大于某个值,那么这一段就一直有,反之,肯定是在一个后缀中改变。
标签:LCP,后缀,Height,数组,排名,sa,rk From: https://www.cnblogs.com/HeNuclearReactor/p/17552212.html