我想，做过几个后缀数组问题的人，都深深理解了要求的sa、rank数组没什么用，真正有用的是height数组。 总结现在遇到的height数组的使用方法。
1 .求字符串双后缀的最长通用前缀
求出后缀I和后缀j最长的共同前缀的长度，即min(height[rank[i] 1]、height[rank[i] 2、height[rank[j]] )，求出rank [ I ] 传递性如果有三个字符串，则按字典顺序排序时，LCP (1，3 )等于min(LCP ) 1，2 )、LCP (2，3 ) )。 上位2字符串的LCP (1，2 )第1位必然不同，且为下位关系。 由于第3个字符串比第2个字符串大，所以第3个字符串和第1个字符串的上位LCP ) 1，2 ) 1位一定是不同的)为了进行分类讨论)，LCP ) 1，3 )=LCP ) 1，2 )又是上位2个字符串的上位LCP )
2 .求出字符串可以重叠的最长的重复子串的长度
给出字符串，求出至少出现两次的可重复的最长子字符串的长度。 首先要最长的话，找出现两次的就足够了。 如果以同样的长度出现三次，那就一定会出现两次。 出现两次就不一定出现过三次。 两次重叠子串的长度必须是两个任意后缀的最长公共前缀的最大值，可以用反证法简单证明。 两个后缀的最长公共前缀的长度是区间height的最小值，因此答案是height数组的最大值。
3 .求出字符串不重复的子串的个数
很明显，合计的子串有n*(n1 )/2个，n是字符串长度。 只需要消除重复的子串，模拟得到的重复子串的数量为sum(height(I ) )、(2个消息)好问题)后缀数组) newdistinctsubstringssport
因此，最终答案是n*(n1 )/2-sum ) height[I] )。
4 .求出两个字符串的最长公共子串
连接两个字符串，在中间插入不出现以免越界的字符，然后发出height，可以得到后缀开始位置在两侧的最大height值。 此外，还可以利用该思想求出k个字符串的最长公共子串。 参考证明： (后缀数组[最大公共子串]长消息poj 2774 _ cloth的博客-CSDN博客