后缀数组求 LCP 和相关证明
一些定义
\(\text{SA}(i)\) 排名为 \(i\) 的后缀左端点；\(\text{rank}(i)\) 左端点为 \(i\) 的后缀排名；\(\text{suf}(i)\) 左端点为 \(i\) 的后缀；
\(\text{lcp}(S,T)\)，串 \(S\) 和 \(T\) 的最长公共前缀，即 \(\max \left \{ x |\forall y\le x, S_{y}=S_{y}\}\right.\)；
\(\text{LCP}(i,j)\)，排名为 \(i\) 的后缀和排名为 \(j\) 的后缀的最长公共前缀，即 \(\text{lcp}(\text{suf}(\text{SA}(i)),\text{suf}(\text{SA}(j)))\)；
\(\text{height}(i)\)，排名为 \(i\) 和 \(i-1\) 的后缀的最长公共前缀，即 \(LCP(i,i-1)\)，特别地 \(\text{height}(1)=0\)；
\(h(i)=\text{height(rank}(i))\)。
性质1
对于 \(1\le i \le n\)，显然有：
\[\text{LCP}(i,i) = n-\text{SA}(i)+1 \]\[\text{LCP}(i,j)=\text{LCP}(j,i) \]定理 1
对于 \(1\le i < j \le n\)，有：
\[\text{LCP}(i,j)=\min_{i<k\le j} \left \{ \text{LCP}(k,k-1) \} \right. \]证明：
引理
对于 \(1\le i < j \le n\)，有：
\[\text{LCP}(i,j)=\min\left \{ \text{LCP}(i,k),\text{LCP}(k,j) \} \right. \text{ } (i\le k\le j) \]证明：
设 \(\min \left \{ \text{LCP}(i,k),\text{LCP}(k,j) \} \right. = p\)，
则 \(\text{LCP}(i,k) \ge p,\text{LCP}(k+1,j)\ge p\)，
所以 \(i\) 和 \(k\) 至少有前 \(p\) 位相等，\(k\) 和 \(j\) 至少有前 \(p\) 位相等，
所以 \(\text{LCP}(i,j) \ge p\)；
又因为$ \min { \text{LCP}(i,k),\text{LCP}(k,j) } = p$，
设 \(\text{suf}(i)=a,\text{suf}(k)=b,\text{suf}(j)=c\)，
则有 \(a_{p+1}\ne b_{p+1}\) 或 \(b_{p+1}\ne c_{p+1}\)，
若 \(a_{p+1} \ne b_{p+1}\) 和 \(b_{p+1} \ne c_{p+1}\) 中仅有一个成立，显然有 \(a_{p+1}\ne c_{p+1}\)，
又根据 \(i,j,k\) 的排名关系，有 \(a_{p+1}\le b_{p+1}\le c_{p+1}\)，
若 \(a_{p+1} \ne b_{p+1}\) 和 \(b_{p+1} \ne c_{p+1}\) 均成立，假设 \(a_{p+1}=c_{p+1}\)，
则有 \(a_{p+1}=b_{p+1}=c_{p+1}\)，与条件矛盾，假设不成立，则 \(a_{p+1}\ne c_{p+1}\)
综上有 \(a_{p+1}\ne c_{p+1}\)，所以 \(\text{LCP}(i,j)\le p\)；
结合 \(\text{LCP}(i,j)\ge p\)，有 \(\text{LCP}(i,j)=p=\min\left \{ \text{LCP}(i,k),\text{LCP}(k,j) \} \right.\)，得证。
根据引理，可推出：
\[\text{LCP}(i,j)=\min\left \{ \text{LCP}(i,k),\text{LCP}(k,j) \} \right. \]\[\text{LCP}(i,j)=\min \left \{ \text{LCP}(i,i+1),\text{LCP}(i+1,j) \} \right. \]\[\text{LCP}(i,j)=\min \left \{ \text{LCP}(i,i+1),\min \left \{ \text{LCP}(i+1,i+2), \text{LCP}(i+2,j)\} \right. \} \right. \]归纳可得：
\[\text{LCP}(i,j)=\min_{i<k\le j} \left \{ \text{LCP} (k,k-1)\} \right. \]得证。
转化
\[\text{LCP}(i,j)=\min_{i<k\le j} \left \{ \text{LCP} (k,k-1)\} \right. = \min_{i<k\le j} \left \{\text{height}_k \} \right. \]这样 \(\text{LCP}\) 问题就转化为区间最值（\(\text{RMQ}\)）问题，可以使用 \(\text{ST}\) 表 \(O(n \log n)\) 预处理 \(O(1)\) 查询。
现在的问题就转化为了求 \(\text{height}\) 数组。
定理 2
对于 \(1<i\le n\)，有：
\[h(i)\ge h(i-1)-1 \]证明：
性质2
对于 \(1\le i,j < n,\text{lcp}(\text{suf}(i),\text{suf}(j))>1\)，有：
\[\text{suf}(i)<\text{suf}(j) \Longleftrightarrow \text{suf}(i+1)<\text{suf}(j+1) \]\[\text{lcp}(\text{suf}(i),\text{suf}(j))-1=\text{lcp}(\text{suf}(i+1),\text{suf}(j+1)) \]定理 1 的引理的推论
对于 \(1\le i,j\le n\)，有：
\[\text{LCP}(i,j)\le\text{LCP}(k,j) \text{ } (i\le k\le j) \]证明：根据定理 1 的引理，显然成立。
当 \(h(i-1)\le 1\) 时，\(h(i)\ge 0\ge h(i-1)-1\)，得证；
当 \(h(i-1) > 1\) 时，即 \(\text{height}(\text{rank}(i-1))>1\)，
可推出 \(\text{rank}(i-1)>1\)，因为 \(\text{height}(1)=0\)，
令 \(j=i-1\)，\(k=\text{SA(rank}(j)-1)\)，有：
\(h(i-1)=\text{LCP}(\text{rank}(j),\text{rank}(k))=\text{lcp}(\text{suf}(j),\text{suf}(k))\)，
\(\text{suf}(k)<\text{suf(j)}\)，
因为 \(\text{lcp}(\text{suf}(j),\text{suf}(k)) = h(i-1)>1\)，根据性质2有：
\(h(i-1)-1=\text{lcp}(\text{suf}(i),\text{suf}(k+1))\)，
\(\text{suf}(k+1)<\text{suf}(i)\)
即 \(\text{rank}(k+1) < \text{rank}(i) \rightarrow \text{rank}(k+1)\le \text{rank}(i)-1\)，
根据定理 1 的引理的推论得：
\[\begin{align} \text{LCP}(\text{rank}(i)-1,\text{rank}(i)) &\ge \text{LCP}(\text{rank}(k+1),\text{rank}(i)) \\ &=\text{lcp}(\text{suf}(i),\text{suf}(k+1)) \\ &= h(i-1)-1 \end{align} \]又因为 \(\text{LCP}(\text{rank}(i)-1,\text{rank}(i))=h(i)\)，所以 \(h(i)\ge h(i-1)-1\)，得证。
具体求法
有了定理 2 后，就可求出 \(\text{height}\) 数组。
先考虑暴力的代码，即从头开始暴力匹配，时间复杂度 \(O(n^2)\)。
根据定理 2，\(h(i)\ge h(i-1)-1\)，可以直接从 \(h(i-1)-1\) 开始匹配。
因为 \(h(i)\le n\)，每次 \(h(i)\) 最多减一，所以时间复杂度 \(O(n)\)。
代码
void get_height() {
for (int i = 1, k = 0, j; i <= n; i ++) {
if (rk[i] == 1) continue; // height[1]=0
k = k ? k - 1 : k; // h[i-1]-1
for (j = sa[rk[i] - 1];
i + k <= n && j + k <= n
&& S[i + k] == S[j + k]; k ++);
height[rk[i]] = k; // k=h[i]=height[rk[i]]
}
}