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

　　10.多个串的公共子串问题 PKU3294

　　首先将串连接起来，然后构造height数组，然后怎么办呢?

　　对，二分答案再判断是否可行就行了。可行条件很直观：有一组后缀，有超过题目要求的个数个不同的字符串中的后缀存在。即，假如题目要求要出现在至少k个串中，那么就得有一组后缀，在不同字符串中的后缀数大于等于k。

　　11、出现或反转后出现所有字符串中的最长子串 PKU1226

　　12、不重叠地至少两次出现在所有字符串中的最长子串

　　之所以把两题一起说，因为它们大同小异，方法在前面的题目均出现过。对于多个串，连起来;反转后出现，将每个字符串反写后和原串都连起来，将反写后的串和原串看成同一个串;求最长，二分答案后height分组;出现在所有字符串中(反写后的也行)，判断方法和10一样，k=n而已;不重叠见问题4，只不过这里对于每个字符串都要进行检验而已。

　　13、两个字符串的重复子串个数。 Pku3415

　　我个人觉得颇有难度的一个问题。具体的题目描述参看Pku3415。

　　14、最后的总结

　　用后缀数组解题有着一定的规律可循，这是后缀的性质所决定的，具体归纳如下：

　　[1] N个字符串的问题(N>1)

　　方法：将它们连接起来，中间用不会出现在原串中的，互不相同的，非0号字符分隔开。

　　[2] 无限制条件下的最长公共子串(重复子串算是后缀们的最长公共前缀)

　　方法：height的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串，才可以直接是height的最大值。

　　[3] 特殊条件下的最长子串

　　方法：二分答案，再根据height数组进行分组，根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len，特殊条件有：

　　<3.1> 出现在k个串中

　　条件：属于不同字符串的后缀个数不小于k。(在一组后缀中，下面省略)

　　<3.2> 不重叠

　　条件：出现在同一字符串中的后缀中，出现位置的最大值减最小值大于等于len。

　　<3.3> 可重叠出现k次

　　条件：出现在同一字符串中的后缀个数大于等于k。若对于每个字符串都需要满足，需要逐个字符串进行判断。

　　[4] 特殊计数

　　方法：根据后缀的性质，和题目的要求，通过自己的思考，看看用后缀数组能否实现。一般和“子串”有关的题目，用后缀数组应该是可以解决的。

　　[5] 重复问题

　　知道一点：lcp(i,i+k)可以判断，以i为起点，长度为k的一个字符串，它向后自复制的长度为多少，再根据具体题目具体分析，得出算法即可。

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)