LCP 与 height
前言阅读此篇前，可先阅读后缀数组
LCP
LCP 就是最长公共前缀，在后缀数组中，\(LCP(i,j)\) 就代表从 \(sa_i\) 开始的后缀和从 \(sa_j\) 开始的后缀的最长公共前缀。
height 的定义
\(height=LCP(sa,sa)\)，即从 \(i\) 开始的后缀与它前一个的后缀的最长公共前缀。
一些性质
\(height] \ge height]-1\)
证明：
当 \(height] \le 1\) 时，很好看出，\(height] \ge 0\)，故正确。
当 \(height] > 1\) 时,因为 \(LCP(i-1,sa-1])=height] > 1\)，那么设这个最长公共为 \(aA\)（其中 \(a\) 代表一个字符 \(A\) 代表一个字符串），从 \(i-1\) 开始的后缀为 \(aAB\)，从 \(sa-1]\) 开始的后缀为 \(aAC\)，所以从 \(i\) 开始的后缀为 \(AB\)，从 \(sa-1]+1\) 开始的后缀就为 \(AC\)，所以 \(LCP(i,sa-1]+1)=|A|\)。设从 \(sa-1]\) 开始的后缀就为 \(D\)。
那么因为 \(aAB > aAC\)，所以 \(AB>AC\)，因为从 \(sa-1]\) 开始的后缀只比从 \(i\) 开始的后缀少一位，那么 \(AB > D \ge AC\)，所以 \(D\) 肯定有一个 \(A\) 的前缀，即 \(height] \ge |A|\)，\(height] \ge height]-1\)
Code
void GetHeight(){ int k=0; for(int i=1;i
页:
[1]