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