国家集训队2003论文集林希德.ppt

求最大重复子串  江苏金陵中学 林希德 题目 举例 数据规模 两个辅助算法 后缀树 问题的转化 算法基本框架 一、字符串分解 S的循环节不能太长 辅助函数和重要结论2 算法基本框架回顾和完善 算法性能分析 总结 举例 B B A A B A B A A B A B B V U 寻找循环周期为5的最优子串 完整循环节 结束位置 举例 B B A A B A B A A B A B B V U 开始位置 长度判定： |S| = 11 = 2 * 5 寻找循环周期为5的最优子串 结束位置 S是合法最优子串 完整循环节 V U 完整循环节 B 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 B A B 长度判定： |S| = 11 = 2 * 5 S是合法最优子串 使用一次“KMP模式匹配的推广算法”在线性时间内求出所有Lp和Ls的函数值 四、枚举所有最优子串 因为：Ls函数定义中，第一个有待比较前缀的字符串总是U Lp函数定义中，第一个有待比较后缀的字符串总是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 字符串分解 answer = 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中的长度 = L End 情况2 2、 For L=1 to |Ui-1 + Ui|-1 do 输出 answer If |LsL| + |LpL| = L Then 用L更新answer的值 * * 字符串W由大写字母组成，W中包含一 些连续出现两次的相同子串，称之为重复子 串。重复子串的大小决定于循环节的长度。 W =“B B A A B A B A A B A B B” A B A A B A B B 循环节长度为3 循环节长度为1 请你求出最大重复子串的循环节长度。 题目 字符串W由大写字母组成，W中包含一 些连续出现两次的相同子串，称之为重复子 串。重复子串的大小决定于循环节的长度。 n = |w| = 100000 O(n2) O(nlg2n) O(n) O(n) KMP模式匹配 O(n+m) 为方便表达，使用 表示开始于位置u结束于位置v的W的子串 W ( u ，v ) 1、S中的字符以L为周期循环出现 S i = S i + L （u = i = v - L） 求出所有最优子串连同它们的周期 定义S是循环周期为L的最优子串，仅当S满足： 2、|S| = 2 L，即S至少包括两个完整循环节。 3、S不能向左扩展， 即u = 1 或者 W(u-1,v)不满足条件1 4、S不能向右扩展， 即 v = n 或者 W(u,v+1)不满足条件1 最大重复子串必然被某个最优子串包含！！ 1、找到S的一个完整