(2)后缀数组的应用--height数组

　　在介绍后缀数组的应用前，先介绍后缀数组的一个重要附属数组：height数组。

　　1、height 数组：定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。height数组是应用后缀数组解题是的核心，基本上使用后缀数组解决的题目都是依赖height数组完成的。

　　2、height数组的求法：具体的求法参见罗穗骞的论文。对于height数组的求法，我并没有去深刻理解，单纯地记忆了而已...有兴趣的朋友可以去钻研钻研再和我交流交流

　　这里给出代码：

　　intrank[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

　　for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

　　return;

　　}

　　3、一些注意事项：height数组的值应该是从height[1]开始的，而且height[1]应该是等于0的。原因是，因为我们在字符串后面添加了一个0号字符，所以它必然是最小的一个后缀。而字符串中的其他字符都应该是大于0的(前面有提到，使用倍增算法前需要确保这点)，所以排名第二的字符串和0号字符的公共前缀(即height[1])应当为0.在调用calheight函数时，要注意height数组的范围应该是[1..n]。所以调用时应该是calheight(r,sa,n)而不是calheight(r,sa,n+1)。要理解清楚这里的n的含义是什么。

　　calheight过程中，对rank数组求值的for语句的初始语句是i=1而不是i=0的原因，和上面说的类似，因为sa[0]总是等于那个已经失去作用的0号字符，所以没必要求出其rank值。当然你错写成for (i=0..)，也不会有什么问题。

　　(3) 后缀数组解题总结

　　1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

　　这个问题是一个特殊求值问题。要认识到这样一个事实：一个字符串中的所有子串都必然是它的后缀的前缀。(这句话稍微有点绕...)对于每一个sa[i]后缀，它的起始位置sa[i]，那么它最多能得到该后缀长度个子串(n-sa[i]个)，而其中有height[i]个是与前一个后缀相同的，所以它能产生的实际后缀个数便是n-sa[i]-height[i]。遍历一次所有的后缀，将它产生的后缀数加起来便是答案。

　　2、后缀的最长公共前缀。(记为lcp(x，y))

　　这是height数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱，正规的说，令x=rank[i],y=rank[j]，x

　　3、最长重复子串(可重叠)

　　要看到，任何一个重复子串，都必然是某两个后缀的最长公共前缀。因为，两个后缀的公共前缀，它出现在这两个后缀中，并且起始位置时不同的，所以这个公共前缀必然重复出现两次以上(可重叠)。而任何两个后缀的最长公共前缀为某一段height值中的最小值，所以最大为height值中的最大值(即某个lcp(sa[i],sa[i+1]))。所以只要算出height数组，然后输出最大值就可以了。

　　4、最长重复不重叠子串 PKU1743

　　这个问题和3的唯一区别在于能否重叠。加上不能重叠这个限制后，直接求解比较困难，所以我们选择二分枚举答案，将问题转换为判定性问题。假设当时枚举的长度为k，那么要怎样判断是否存在长度为k的重复不重叠子串呢?

　　首先，根据height数组，将后缀分成若干组，使得每组后缀中，后缀之间的height值不小于k。这样分组之后，不难看出，如果某组后缀数量大于1，那么它们之中存在一个公共前缀，其长度为它们之间的height值的最小值。而我们分组之后，每组后缀之间height值的最小值大于等于k。所以，后缀数大于1的分组中，有可能存在满足题目限制条件的长度不小于k的子串。只要判断满足题目限制条件成立，那么说明存在长度至少为k的合法子串。

　　对于本题，限制条件是不重叠，判断的方法是，一组后缀中，起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置>=k。满足这个条件的话，那么这两个后缀的公共前缀不但出现两次，而且出现两次的起始位置间隔大于等于k，所以不会重叠。

　　5、最长的出现k次的重复(可重叠)子串。 PKU3261

　　使用后缀数组解题时，遇到“最长”，除了特殊情况外(如问题3)，一般需要二分答案，利用height值进行分组。本题的限制条件为出现k次。只需判断，有没有哪一组后缀数量不少于k就可以了。相信有了我前面问题的分析作为基础，这个应该不难理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了，可以找个具体的例子来分析分析。

　　6、最长回文子串 ural1297

　　这个问题没有很直接的方法可以解决，但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后，我们要做的，是要求出以i为中心的回文子串最长为多长。利用后缀数组，可以设计出这样一种求法：求i往后的后缀与i往前的前缀的最长公共前缀。我这里的表述有些问题，不过不影响理解。

　　要快速地求这个最长前缀，可以将原串反写之后接在原串后面。在使用后缀数组的题目中，连接两个(n个)字符串时，中间要用不可能会出现在原串中，不一样的非0号的字符将它们隔开。这样可以做到不影响后缀数组的性质。然后，问题就可以转化为求两个后缀的最长公共前缀了。具体的细节，留给大家自己思考...(懒...原谅我吧，都打这么多字了..一个多小时了啊TOT)