后缀数组的一些性质height数组

　　height数组&＃xff1a;定义 height[i] &＃61; suffix[i-1] 和 suffix[i] 的最长公共前缀&＃xff0c;也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k 不妨设 Rank[j]

　　suffix[j] 和 suffix[k] 的最长公共前缀为 height[Rank[j]&＃43;1] , height[Rank[j]&＃43;2],......,height[Rank[k]] 中的最小值。

　　例如&＃xff0c;字符串为“aabaaaab”&＃xff0c;求后缀“abaaaab”和后缀“aaab”的最长公共前缀&＃xff0c;如图4所示&＃xff1a;

　　那么应该如何高效的求出height值呢&＃xff1f;

　　定义 h[i] &＃61; height[Rank[i]]&＃xff0c;也就是suffix(i)和它前一名的最长公共前缀。

　　h数组有以下性质&＃xff1a;h[i]>&＃61;h[i-1]-1.

　　证明&＃xff1a;

　　设suffix[k]是排在suffix[i-1]前一名的后缀&＃xff0c;则它们的最长公共前缀是h[i-1]。那么suffix[k&＃43;1]将排在suffix[i]前面&＃xff08;这里要求h[i-1]>1&＃xff0c;如果h[i-1]<&＃61;1原式显然成立&＃xff09;并且suffix[k&＃43;1]和suffix[i]的最长公共前缀是h[i-1]-1&＃xff0c;所以suffix(i)和它前一位的最长公共前缀至少是h[i-1]-1。

　　实现的时候没必要保存h数组&＃xff0c;只需按照h[1],h[2],h[3],...,h[n]的顺序计算即可。

　　代码&＃xff1a;