《国家集训队2003论文集林希德》由会员分享，可在线阅读，更多相关《国家集训队2003论文集林希德（38页珍藏版）》请在金锄头文库上搜索。
1、求最大重复子串江苏金陵中学 林希德题目字符串W由大写字母组成，W中包含一 些连续出现两次的相同子串，称之为重复子 串。重复子串的大小决定于循环节的长度。W =“B B A A B A B A A B A B B”A B A A B A举例= 2 L，即S至少包括两个完整循环节。3、S不能向左扩展，即u = 1 或者 W(u-1,v)不满足条件14、S不能向右扩展，即 v = n 或者 W(u,v+1)不满足条件1最大重复 子串必然 被某个最 优子串包 含！算法基本框架1、找到S的一个完整循环节 2、根据循环节将S分别向左、向右扩展到不能扩展为止3、判断扩展以后的S是否长度 = 2 L如果是，则
2、认为找到了一个循环周期为L 的最优子串S。?如果字母Q1从未在P中出现过,那么 Ui = Q1否则 Ui = P中出现过的Q的最长前缀一、字符串分解Ui-1PQUi-2U1字符串W将W分解成 W = U1 + U2 + U3 + + Um 的形式，其中 Ui定义如下： W = P + QP = U1 + U2 + + Ui-1 Q1只要字符串x 的开始位置在 P内，就认为x 在P中出现过 ！A B A A B A B A A B A B B 举例PQAA B A A B A B A A B A A B 举例PQBA B A A B A B A A B A A B 举例PQAAA B A A B
3、 A B A A B A A B 举例PQA B A A B AA B A A B A B A A B A A B 举例PQB A A B A B A A B AA B A A B A B A A B A A B 举例PQA B A A B A B A A B A A B 举例字符串分解过程借助“后缀树”算法实现A B A B怎样利用字符串分解的特殊定义找到最优子 串S的一个完整循环节呢？ S的循环节能有多长呢?分类讨论。二、寻找完整循环节问题：S的开始位置在何处呢？ 解决方法：假设S的结束位置在固定片断Ui内一定要记 住：整数i 是个已知 常量！a. S的开始位置也在Ui内. Ui在P中某处
4、出现过 S在P中某处出现过 为避免重复工作，此情况不予考虑！最优子串SUi PQS的开始位置不能太迟这里用到了字符串分解的定义最优子串Sb. 最末循环节包含Ui-1UiUi-1 PQ最末循环节红色和绿色线段标示了相同的子串 根据定义，|Ui-1| = 红色线段 矛盾，情况b不存在。S的循环节不能太长这里再次用到了字符串分解的定义Ui-1最优子串Sc. |S位于Ui-1之前的子串| = 循环周期LUiUi-1 PQ最末循环周期红色和绿色线段标示了相同子串 根据定义，|Ui-1| = 红色线段 矛盾，情况c也不存在。S的开始位置不能太早这里又一次用到了字符串分解的定义重要结论11. S的开始位置早
5、于Ui且最末循环节没有将Ui-1包含在内，故L = 2，故下列两种情况S必居其一：情况1. S在V中的长度 = L情况2. S在U中的长度 = L 最优子串SUi实际就是的一个完整循环节U(1,L)这个结 论很重 要！找到循环节了!VU最优子串S1、尽量向右扩展 三、循环节扩展和长度判定完整循环节2、尽量向左扩展 3、如果扩展以后的|S| = 2L，那么S是最优子串。U(1,L)实际就是的一个完整循环节找到循环节了!B B A A B A B A A B A B B 举例VU寻找循环周期为5的最优子串完整循环节举例B B A A B A B A A B A B B VU寻找循环周期为5的最优子
6、串完整循环节举例B B A A B A B A A B A B B VU寻找循环周期为5的最优子串完整循环节举例B B A A B A B A A B A B B VU结束 位置寻找循环周期为5的最优子串完整循环节举例B B A A B A B A A B A B B VU寻找循环周期为5的最优子串完整循环节结束 位置举例B B A A B A B A A B A B B VU寻找循环周期为5的最优子串完整循环节结束 位置举例B B A A B A B A A B A B B VU寻找循环周期为5的最优子串完整循环节结束 位置举例B B A A B A B A A B A B B VU寻找循环
7、周期为5的最优子串完整循环节结束 位置举例B B A A B A B A A B A B B VU开始 位置长度判定：|S| = 11 = 2 * 5寻找循环周期为5的最优子串结束 位置S是合法最优子串完整循环节VU完整循环节辅助函数和重要结论2B B A A B A B A A B A B B LsL = U 与U(1+L，|U|)的最长公共前缀 LpL = V 与V + U(1，L)的最长公共后缀 当且仅当|LsL + LpL| = L时 存在唯一的周期为L的最优子串LsL + U(1,L) + LpL A B向右扩展B A A B向左扩展长度判定B A A BA B长度判定：|S| =
8、11 = 2 * 5S是合法最优子串使用一次“KMP模式匹配的推广算法” 在线性时间内求出所有Lp和Ls的函数值四、枚举所有最优子串因为：Ls函数定义中，第一个有待比较前缀的字符串总是ULp函数定义中，第一个有待比较后缀的字符串总是V所以：我们可以然后：从 1 到 |Ui + Ui-1| 枚举循环节的长度L，并在枚举的同时判断是否 |LsL + LpL| = L，即可： 找出所有最优子串连同它们的周期。这样Lp和Ls函 数的平摊求解 复杂度为O(1) LsL = 与U(1+L，|U|)的最长公共前缀 LpL = 与V + U(1，L)的最长公共后缀 U V 算法基本框架回顾和完善字符串分解 a
9、nswer = 0令 V = 长度为 |Ui| + 2 * |Ui-1|的P的后缀U = Ui For i = 2 to m do End For针对情况1：S在V中的长度 = L End 情况1 1、 求出函数Ls和函数Lp的值针对情况2：S在U中的长度 = LEnd 情况22、 For L=1 to |Ui-1 + Ui|-1 do 输出 answerIf |LsL| + |LpL| = LThen 用L更新answer的值 算法性能分析较大 20 101、字符串分解O (n)O (n)程序步骤 算法名称 复杂度常数因子后缀树算法 2、辅助函数3、枚举所有最优子串 O (n)Sum2(|Ui-1|+|Ui|) = 4n KMP模式匹配Sum|Ui-1|+|Ui| = 2n 枚举总结 掌握基础算法 善于分化问题 融会贯通谢 谢 !
