2011年软考程序员考试复习笔试知识点整理(16)2

 　(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=k。满足这个条件的话，那么这两个后缀的公共前缀不但出现两次，而且出现两次的起始位置间隔大于等于k，所以不会重叠。

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

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

　　6、最长回文子串 ural1297

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

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