上集 : 后缀数组 I —— 后缀排序
记 \(S_i\) 表示以 \(i\) 为起点的后缀， \(sa_i\) 表示对 \(s\) 进行后缀排序后排名为 \(i\) 的后缀，\(SA_i\) 表示对 \(s\) 进行后缀排序后排名为 \(i\) 的后缀的起点，\(rk_i\) 表示对 $S_i $ 进行后缀排序后的排名，\(lcp(s_1,s_2)\) 代表 \(s_1\) 和 \(s_2\) 的最长公共前缀的长度。
我们接下来要考察关于所有后缀的 \(\operatorname{lcp}\) 的性质。
性质 \(1\) : \(\operatorname{lcp}(sa_i,sa_k)=\min(\operatorname{lcp}(sa_i,sa_j),\operatorname{lcp}(sa_j,sa_k))(i<j<k)\)。
下面简略证明，记 \(p=\min(\operatorname{lcp}(sa_i,sa_j),\operatorname{lcp}(sa_j,sa_k))\)，可知 \(sa_i\) 和 \(sa_j\) 的前 \(p\) 位相等，\(sa_j\) 和 \(sa_k\) 的前 \(p\) 位相等。由此，\(sa_i\) 和 \(sa_k\) 的前 \(p\) 位相等，所以 \(\operatorname{lcp}(sa_i,sa_k)\ge p\)。
考虑分析 \(sa_i\) 和 \(sa_k\) 的第 \(p+1\) 位，记 \(sa_i,sa_j,sa_k\) 的第 \(p+1\) 位分别为 \(w_i,w_j,w_k\)，分三种情况讨论：
-
\(\operatorname{lcp}(sa_i,sa_j)=\operatorname{lcp}(sa_j,sa_k)=p\)，由此可得第 \(p+1\) 位 \(sa_i\) 和 \(sa_j\) 不同，而之前的 \(p\) 位都相同，并且 \(sa_i\) 的排名显然高于 \(sa_j\)，所以有 \(w_i<w_j\)，同理有 \(w_j<w_k\)，从而有 \(w_i<w_k\)。
-
\(\operatorname{lcp}(sa_i,sa_j)>\operatorname{lcp}(sa_j,sa_k)=p\)，有 \(w_i=w_j\)，有 \(w_j<w_k\)，从而有 \(w_i<w_k\)。
-
\(\operatorname{lcp}(sa_j,sa_k)>\operatorname{lcp}(sa_i,sa_j)=p\)，有 \(w_i<w_j\)，有 \(w_j=w_k\)，从而有 \(w_i<w_k\)。
可以发现，无论如何总有 \(w_i<w_k\)，从而有 \(\operatorname{lcp}(sa_i,sa_j)\leq p\)，又因为 \(\operatorname{lcp}(sa_i,sa_j)\ge p\)，故得证。
性质 \(2\) ： \(\operatorname{lcp}(sa_i,sa_j)=\min\limits_{k=i+1}^j\operatorname{lcp}(sa_{k-1},sa_k)(i<j)\)。
这个性质由性质 \(1\) 可以简单推得，考虑根据这个性质定义一个数组 \(height_i=\operatorname{lcp}(sa_{i-1},sa_i)\)，式子变成了 \(\operatorname{lcp}(sa_i,sa_j)=\min\limits_{k=i+1}^j height_k\)，通过这一步转化。我们将求 \(\operatorname{lcp}\) 转化为了求区间 \(\min\)，毫无疑问，这十分有用。
性质 \(3\) ： \(\operatorname{lcp}(sa_j,sa_i)\ge\operatorname{lcp}(sa_k,sa_i)(k\leq j\leq i)\)。
这个性质由性质 \(2\) 可以简单推得，这个性质说明了 \(\operatorname{lcp}\) 在固定右端点的情况下满足单调性。
接下来我们还面临着一个问题，我们在性质 \(2\) 中引入了 \(height\) 数组，但是如何求 \(height\) 数组呢？
有一种较为暴力的 \(O(n\log n)\) 的方法，即 hash + 二分，时间复杂度方面由于后缀数组本身自带 \(\log\) 完全不会成为复杂度瓶颈。
不过，存在一种巧妙的 \(O(n)\) 求解方法。
记 \(h_i=height_{rk_i}\)，即 \(h_i\) 代表 \(S_i\) 与 \(sa_{rk_i-1}\) 的最长公共前缀。
接下来我们需要证明 \(h_i\ge h_{i-1}-1\)。
当 \(h_{i-1}\leq1\) 时，显然成立。
当 \(h_{i-1}>1\) 时，考虑 \(h_{i-1}-1\) 的意义是什么，即将 \(S_{i-1}\) 的开头字符抹掉之后的最长公共前缀，我们发现，将 \(S_{i-1}\) 的开头字符抹掉即 \(S_i\)，另一个后缀同理，可得 \(h_{i-1}-1=\operatorname{lcp}(S_i,S_{SA_{rk_{i-1}}+1})\)。
所以证明 \(h_i\ge h_{i-1}-1\) 变成了证明 \(\operatorname{lcp}(sa_{rk_i-1},S_i)\ge\operatorname{lcp}(S_{SA_{rk_{i-1}}+1},S_i)\)。
由于 \(S_{i-1}>sa_{rk_{i-1}-1}\)，而它们又有公共前缀 （因为有条件 \(h_{i-1}>1\)），所以将第一个字符删掉之后，仍保持单调性，故有 \(S_i>S_{SA_{rk_{i-1}}+1}\)，又因为 \(sa_{rk_i-1}\) 的排位仅在 \(S_i\) 前一位，而 \(S_{SA_{rk_{i-1}}+1}\) 的排位在 \(S_i\) 前，所以一定有 \(S_{SA_{rk_{i-1}}+1}\leq sa_{rk_i-1}\)，根据性质 \(3\) 有 \(\operatorname{lcp}(sa_{rk_i-1},S_i)\ge\operatorname{lcp}(S_{SA_{rk_{i-1}}+1},S_i)\)，从而 \(h_i\ge h_{i-1}-1\) 得证。
根据这个性质，我们可以得到 \(h\) 数组的求法，即暴力，我们在暴力计算 \(h_i\) 的时候已经知道前 \(h_{i-1}-1\) 位一定不用看，暴力往后匹配，若未能匹配成功则停止，由均摊分析可知总复杂度为 \(O(n)\)。
标签：lcp,后缀,height,II,ge,数组,sa,operatorname,rk From： https://www.cnblogs.com/Miracle-blog/p/17042935.html