最长重复子串

《最长重复子串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最长重复子串湖南长沙市雅礼中学龙凡【关键词】扩展KMP算法二分后缀数组后缀树【引言】近些年来，字符串类型的试题越来越多的出现在信息学竞赛中。而字符串处理中常常出现的一类问题即——最长重复子串。本文将讨论最长重复子串问题及它的几种变形，并给出实际应用中效果较好的解决该类问题的几种方法。文中将涉及到使用扩展KMP、后缀数组等工具性算法。这些算法的具体方法与实现请参考近年来的国家集训队论文。【连续最长重复子串】1.问题描述给定一个长度为N的字符串S。记为S的第I个字符到第J个字符所组成的子串。若存在，则称S存在一个长度为K的连续重复子串。现在要你求出K的最大值，满足存在一个

2、值I使得。2.基于二分的算法枚举K，然后扫描的方法的时间复杂度高达O(N2)，效果并不能让人满意。我们需要更高效的算法，这里给出一个基于二分结合扩展KMP算法的算法，时间复杂度为O(Nlog2N)。在介绍主算法之前，我们先来简要介绍扩展KMP算法，这里并不对扩展KMP算法具体如何实现进行介绍，仅仅为了方便读者理解，介绍扩展KMP算法的功能。具体的扩展KMP算法的实现，请参考2003年国家集训队林希德的论文。扩展KMP算法：对于一个主串S，和一个模式串T。记。而扩展KMP算法可以在O(Len(S)+Len(T))时间复杂度内求解q(1)…q(len(s))。现在回到主算

3、法，对于一个给定的串S。设Ans(S)为该串的连续最长重复子串长度。那么可以知道：其中Cross(l,r,mid)表示：在s(l,r)中，包含s(mid)和s(mid+1)这两个字符的连续最长重复子串长度。根据上面的性质，我们二分求解Ans(S(l,r))，令。如果我们能够在O(r-l)的时间复杂度内求解Cross(l,r,mid)，则我们可以在O(nlog2n)的时间复杂度内求解Ans(s(1,n))。我们分两种情况来讨论包含s(mid)、s(mid+1)这两个字符的连续重复子串的出现情况：1．设重复情况为，且。……lrmidj注意上图，红色的分界线表示mid的分界

4、线。这是一个k=4时候的情况，注意到图中黄色的部分和蓝色的部分要求对应相等。我们枚举mid在重复子串中的对称位置j（用绿色的分界线表示），从图中可以我们总结出连续重复子串的出现条件：设West(j)表示当Mid的对称位置为j时，图中黄色相等部分可以延伸的长度。设East(j)表示当Mid的对称位置为j-1时，图中蓝色相等部分可以延伸的长度。则：当我们枚举了Mid的对称位置j，当且仅当时，存在一个连续重复子串长度k=mid-j的连续重复子串。2．设重复情况为，且……lrmidj与情况1类似，枚举了mid的对称位置j之后。当且仅当时存在一个连续重复子串长度k=j-mid的

5、连续重复子串。可以知道，在预先算出了West(l)…West(r)和East(l)…East(r)数组之后，处理上述两种情况的时间复杂度为O(r-l)。那么如何预先算出West数组和East数组呢？通过分析我们发现：设Rotate(S)表示S字符串的逆字符串：比如Rotate(‘123’)=Rotate(‘321’)。则West数组事实上是Rotate(s(l,r))作为母串，Rotate(s(l,mid))作为模式串时，扩展KMP算法求得的Q数组。而East数组则是S(l,r)作为母串，s(mid+1,r)作为模式串时，扩展KMP算法求得的Q数组。我们只要预先执行两

6、次扩展KMP算法，就能在O(r-l)的时间复杂度内求得West数组和East数组。那么我们计算Corss(l,r,mid)的时间复杂度也为O(r-l)，也就是说我们可以利用二分配合扩展KMP算法在O(Nlog2N)的时间复杂度内求得Ans(S(1,n))，即我们要求的答案。1.其他解决方法上面，我们给出了O(Nlog2N)的时间复杂度内利用二分＋扩展KMP求解连续最长重复子串的算法。事实上，这道题目利用后缀树配合扩展KMP，可以在O(N*Log2Σ)的时间复杂度内解决（其中Σ是字符串涉及的字符集大小）。由于后缀树实现较为复杂，并且对空间要求较高，这里就不作介绍了。有兴

7、趣的读者可以参考2003年国家集训队员林希德的论文。【连续重复子串的扩展】1．问题的扩展给出一个长度为N的字符串S以及整数g。有多少对不同的i、j使得：，且。题目来源：UVA10829L-GapSubstring，原题2．算法分析这道题目相比经典的连续最长重复子串问题，有两点不同：1.题目中有一个g的参量，这个参量的意义相当于两个重复子串之间的间隔长度。当g=0时即连续重复子串。2.题目需要我们给出的是长度大于1的重复子串的个数，而不是最长重复子串的长度。我们仍然尝试使用二分配合扩展KMP算法的方法来求解该问题。设Ans(s)为字符串S满足题目条件的