最长重复子串.doc

最长重复子串 湖南长沙市雅礼中学 龙凡【关键词】扩展KMP算法 二分 后缀数组 后缀树【引言】近些年来，字符串类型的试题越来越多的出现在信息学竞赛中。而字符串处理中常常出现的一类问题即最长重复子串。本文将讨论最长重复子串问题及它的几种变形，并给出实际应用中效果较好的解决该类问题的几种方法。文中将涉及到使用扩展KMP、后缀数组等工具性算法。这些算法的具体方法与实现请参考近年来的国家集训队论文。【连续最长重复子串】1. 问题描述给定一个长度为N的字符串 S。记 为S的第I个字符到第J个字符所组成的子串。若存在，则称S存在一个长度为K的连续重复子串。现在要你求出K的最大值，满足存在一个值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)。现在回到主算法，对于一个给定的串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的分界线。这是一个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的连续重复子串。可以知道，在预先算出了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数组。我们只要预先执行两次扩展KMP算法，就能在O(r-l)的时间复杂度内求得West数组和East数组。那么我们计算Corss(l,r,mid)的时间复杂度也为O(r-l)，也就是说我们可以利用二分配合扩展KMP算法在O(N log2N)的时间复杂度内求得Ans(S(1,n)，即我们要求的答案。3. 其他解决方法上面，我们给出了O(N log2N)的时间复杂度内利用二分扩展KMP求解连续最长重复子串的算法。事实上，这道题目利用后缀树配合扩展KMP，可以在O(N*Log2)的时间复杂度内解决（其中是字符串涉及的字符集大小）。由于后缀树实现较为复杂，并且对空间要求较高，这里就不作介绍了。有兴趣的读者可以参考2003年国家集训队员林希德的论文。【连续重复子串的扩展】1 问题的扩展给出一个长度为N的字符串S以及整数g。有多少对不同的i、j使得：，且。题目来源：UVA 10829 L-Gap Substring，原题2 算法分析这道题目相比经典的连续最长重复子串问题，有两点不同：1. 题目中有一个g的参量，这个参量的意义相当于两个重复子串之间的间隔长度。当g=0时即连续重复子串。2. 题目需要我们给出的是长度大于1的重复子串的个数，而不是最长重复子串的长度。我们仍然尝试使用二分配合扩展KMP算法的方法来求解该问题。设Ans(s)为字符串S满足题目条件的重复子串个数。和连续重复子串经典问题一样，我们有：这里，我们设Cross(l,r,mid)为s(l,r)满足题目条件且包含s(mid)、s(mid+1)这两个字符的重复子串个数。于是我们剩下的中心问题，又是如何快速的求解Cross(l,r,mid)。由于引入了间隔的因素，我们分三种情况讨论。a. 重复子串的中心间隔部分在左侧lrmidj上图中，蓝色、黄色为对应的相同部分。而绿色则是两个重复子串的间隔部分我们同样枚举mid的对称位置j，并依照经典的连续重复子串的方法进行预处理，求出West、East数组。但是我们要注意的是，这道题目要计算的是重复子串的数目。那么对于每个枚举的对称位置J，我们需要的是统计下面的不定方程有多少组解：注意由于重复子串必须要包含s(mid+1)这个字符，所以L2不能为0。求解上面这个带限制条件的不定方程的整数解的数目（L1、L2是未知数，即黄、蓝两种颜色延伸的长度。）可以在O(1)的时间复杂度内解决。b. 重复子串的中心间隔部分在右侧由于和第一种情况完全类似，这里跳过。c. 重复子串的中心间隔部分跨越s(mid)、s(mid+1)这是最复杂的情况，下面是一个例子：lrmid 我们没有办法套用经典的求解连续最长公共子串的方法，因为由于间隔部分跨越了s(mid)、s(mid+1)。也就是说，根本就不存在Mid位置的对称位置。因为间隔部分在重复子串中本来就是不对称的。我们并没有什么好方法解决这种情况。 唯一的方法就是，先枚举间隔串的具体位置。然后对于每一种不同的位置，分别做一次扩展KMP算法进行解决。这样做的时间复杂度为O(r-l)*g)。 由于第三种情况的时间复杂度为O(r-)*g)，求解Ans(s(1,n)的总时间复杂度为O(g*N log2N)。通过适当的优化，已经可以通过UVA题库的官方数据。3 进一步优化上面，我们借鉴经典连续重复子串的算法，得到了一个O(g*n log2n)时间复杂度的算法。算法的瓶颈在于第三种情况的处理，它需要花费O(g*(r-l)的时间复杂度。我们来深入分析c情况：lrmidmid+g-1j 考虑到第三种情况之所以麻烦，就是因为绿色的间隔部分跨越了红色的分界线，以至于无法借鉴经典算法，枚举分界位置在重复子串中的对称位置。为了解决这个情况，我们强制将分界线向右移动g-1位，这样绿色的间隔部分又再次落在了分界线的左边，我们可以按照类似第一种情况的处理方法来处理第三种情况，时间复杂度为O(r-l)。然而这样的强制移动是有代价的，下面的情况我们没有考虑到：lrmidmid+g-1可以看出，重复子串根本就没有跨越我们强制向右移动之后的分界线！我们必须要特别处理这种情况，由于这时候重复子串的长度已经被严格限制在了3g范围内。我们可以仍然采用原先的方法，枚举间隔串的具体位置，并对于每种位置进行一次扩展KMP算法。时间复杂度为O(g2)，注意到，使用扩展KMP由于常数系数比较大，往往效果还不如直接朴素匹配划算，时间复杂度为O(g3)。由于第三种情况的时间复杂度降为O(r-l)+g2)，那么求解Ans(s(1,n)的时间复杂度为O(N log2N+Ng2)。这样，我们就在O(N log2N+Ng2)解决了这个问题。该程序可以在1.5s内通过UVA的所有数据。事实上，第三种情况使用朴素匹配的效果就这道题目来说，比使用扩展KMP更好，当然理论时间复杂度是O(N log2N+Ng3)。【任意最长重复子串问题】1 问题描述给定一个长度为N的字符串S，请你求出k的最大值,使得存在i、j满足：且2 算法分析简单的说，这道题目是求任意最长重复子串，并且要求重复的子串不互相重叠。由于任意重复子串出现的随意性，难以再套用二分+扩展KMP的方法解决。下文将提出一个使用后缀数组的时间复杂度为O(N log2N)的算法。在介绍主算法之前，这里先简要介绍后缀数组的功能。设，我们将Suffix(i)排序，字典顺序第i个的后缀记为Suffix(Pos(i)，即：同时，我们设，即Suffix(i)与Suffix(j)的公共前缀长度。同时记，根据Lcp定理：。针对一个给定的字符串S，后缀数组可以在O(N log2N)的时间复杂度内，求出Pos和Height数组。相应的后缀数组的实现的具体算法以及Lcp定理及其证明，可以参考2004年国家集训队员许智磊的论文。现在回到原问题上，我们来分析一下最长重复子串的出现条件：且等价于：且，由于k完全占据了条件不等式的右边，我们考虑二分枚举答案k。然后再判断是否存在长度为k的最长重复子串。即是否存在i、j满足条件。我们设计如下算法，一次扫描判断是否存在满足条件的i、j：1. Min、Max0。2. 依次检查height(1)height(n-1)。3. 若height(i)k则重置：Min、Max0。否则更新Min、Max，若MaxPos(i)则MinPos(i)。4. 直到将height(1)height(n-1)扫描完毕，在算法执行过程中，若出现，则存在长度为k的最长重复子串，否则就不存在。上述的算法，黑体字部分的理由是：若出现了。则当i=min、j=max时满足最长重复子串的出现条件。而斜体字部分，正是为了保证而将Max和Min重置的。因为Height(i)i，根据lcp定理均有。一次扫描的时间复杂度为O(N)，那么在用O(N log2N)构建了后缀数组之后，我们可以在O(N log2N)的时间复杂度内通过二分枚举答案+判断的方法求出最长重复子串的长度。总时间复杂度为O(N log2N)。【总结】重复子串是一类具有代表性的字符串处理问题，相应的算法也很具有可推广性。通过研究该问题及其相关变形，可以得到很多适用于一类字符串问题的方法和技巧。本文所介绍的算法并非理论上的最优算法，而是在实践中，相对效果较且好容易实现的方法。算法是思维的结晶，不同得思维