height数组：定义 height[i] = suffix[i-1] 和 suffix[i] 的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k 不妨设 Rank[j] < Rank[k] ，则有以下性质：
suffix[j] 和 suffix[k] 的最长公共前缀为 height[Rank[j]+1] , height[Rank[j]+2],......,height[Rank[k]] 中的最小值。
例如，字符串为“aabaaaab”，求后缀“abaaaab”和后缀“aaab”的最长公共前缀，如图4所示：
那么应该如何高效的求出height值呢？
定义 h[i] = height[Rank[i]]，也就是suffix(i)和它前一名的最长公共前缀。
h数组有以下性质：h[i]>=h[i-1]-1.
证明：
设suffix[k]是排在suffix[i-1]前一名的后缀，则它们的最长公共前缀是h[i-1]。那么suffix[k+1]将排在suffix[i]前面（这里要求h[i-1]>1，如果h[i-1]<=1原式显然成立）并且suffix[k+1]和suffix[i]的最长公共前缀是h[i-1]-1，所以suffix(i)和它前一位的最长公共前缀至少是h[i-1]-1。
实现的时候没必要保存h数组，只需按照h[1],h[2],h[3],...,h[n]的顺序计算即可。
代码：
int rank[maxn],height[maxn]; void calheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); return; }