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

　　7、求一个串最多由哪个串复制若干次得到 PKU2406

　　具体的问题描述请参考PKU2406.这个问题可以用KMP解决，而且效率比后缀数组好。

　　利用后缀数组直接解决本题也很困难(主要是，就算二分答案，也难以解决转变而成的判定性问题。上题也是)，但可以同过枚举模板串的长度k(模板串指被复制的那个串)将问题变成一个后缀数组可以解决的判定性问题。首先判断k能否被n整除，然后只要看lcp(1,k+1)(实际在用c写程序时是lcp(0,k))是否为n-k就可以了。

　　为什么这样就行了呢?这要充分考虑到后缀的性质。当lcp(1，k+1)=n-k时，后缀k+1是后缀1(即整个字符串)的一个前缀。(因为后缀k+1的长度为n-k)那么，后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符，又相当于后缀k+1的前k个字符，所以与后缀1的前k个字符对应相同，且和后缀k的k+1..2k又对应相同。依次类推，只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值，就可以得到n/k的最大值了。

　　8、求两个字符串的最长公共子串。Pku2774、Ural1517

　　首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的，后者是可以不连续的。

　　对于两个字符串的问题，一般情况下均将它们连起来，构造height数组。然后，最长公共子串问题等价于后缀的最长公共前缀问题。只不过，并非所有的lcp值都能作为问题的答案。只有当两个后缀分属两个字符串时，它们的lcp值才能作为答案。与问题3一样，本题的答案必然是某个height值，因为lcp值是某段height值中的最小值。当区间长度为1时，lcp值等于某个height值。所以，本题只要扫描一遍后缀，找出后缀分属两个字符串的height值中的最大值就可以了。判断方法这里就不说明了，留给大家自己思考...

　　9、重复次数最多的重复子串 SPOJ 687，Pku3693

　　难度比较大的一个问题，主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考Pku3693.

　　又是一题难以通过二分枚举答案解决的问题(因为要求的是重复次数)，所以选择朴素枚举的方法。先枚举重复子串的长度k，再利用后缀数组来求长度为k的子串最多重复出现多少次。注意到一点，假如一个字符串它重复出现2次(这里不讨论一次的情况，因为那是必然的)，那么它必然包含s[0],s[k],s[2*k]...之中的相邻的两个。所以，我们可以枚举一个数i，然后判断从i*k这个位置起的长度为k的字符串能重复出现多少次。判断方法和8中的相似，lcp(i*k,(i+1)*k)/k+1。但是，仅仅这样会忽略点一些特殊情况，即重复子串的起点不在[i*k]位置上时的情况。这种情况应该怎么求解呢?看下面这个例子：

　　aabababc

　　当k=2，i=1时，枚举到2的位置，此时的重复子串为ba(注意第一位是0),lcp(2，4)=3，所以ba重复出现了2次。但实际上，起始位置为1的字符串ab出现次数更多，为3次。我们注意到，这种情况下，lcp(2,4)=3，3不是2的整数倍。说明当前重复子串在最后没有多重复出现一次，而重复出现了部分(这里是多重复出现了一个b)。如果我这样说你没有看懂，那么更具体地：

　　sa[2]=bababc

　　sa[4]=babc

　　lcp=bab

　　现在注意到了吧，ba重复出现了两次之后，出现了一个b，而a没有出现。那么，不难想到，可以将枚举的位置往前挪一位，这样这个最后的b就能和前面的一个a构成一个重复子串了，而假如前挪的一位正好是a，那么答案可以多1。所以，我们需要求出a=lcp(i*k,(i+1)*k)%n，然后向前挪k-a位，再用同样的方法求其重复出现的长度。这里，令b=k-a,只需要lcp(b,b+k)>=k就可以了。实际上，lcp(b,b+k)>=k时，lcp(b,b+k)必然大于等于之前求得的lcp值，而此时答案的长度只加1。没有理解的朋友细细体会下上图吧。

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

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

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