算法合集之《寻找最大重复子串》.ppt

求最大重复子串江苏金陵中学林希德 题目 字符串W由大写字母组成 W中包含一些连续出现两次的相同子串 称之为重复子串 重复子串的大小决定于循环节的长度 W BBAABABAABABB ABAABA 举例 BB 循环节长度为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为周期循环出现Si Si L u i v L 求出所有最优子串连同它们的周期 定义S是循环周期为L的最优子串 仅当S满足 2 S 2L 即S至少包括两个完整循环节 3 S不能向左扩展 即u 1或者W u 1 v 不满足条件14 S不能向右扩展 即v n或者W u v 1 不满足条件1 最大重复子串必然被某个最优子串包含 算法基本框架 1 找到S的一个完整循环节 2 根据循环节将S分别向左 向右扩展到不能扩展为止 3 判断扩展以后的S是否长度 2L 如果是 则认为找到了一个循环周期为L的最优子串S 如果字母Q1从未在P中出现过 那么Ui Q1否则Ui P中出现过的Q的最长前缀 一 字符串分解 Ui 1 P Q Ui 2 U1 字符串W 将W分解成W U1 U2 U3 Um的形式 其中Ui定义如下 W P Q P U1 U2 Ui 1 Q1 只要字符串x的开始位置在P内 就认为x在P中出现过 ABAABABAABABB 举例 P Q A ABAABABAABAAB 举例 P Q B ABAABABAABAAB 举例 P Q A A ABAABABAABAAB 举例 P Q ABA ABA ABAABABAABAAB 举例 P Q BAABA BAABA ABAABABAABAAB 举例 P Q ABAABABAABAAB 举例 字符串分解过程借助 后缀树 算法实现 AB AB 怎样利用字符串分解的特殊定义找到最优子串S的一个完整循环节呢 S的循环节能有多长呢 分类讨论 二 寻找完整循环节 问题 S的开始位置在何处呢 解决方法 假设S的结束位置在固定片断Ui内 一定要记住 整数i是个已知常量 S的开始位置也在Ui内 Ui在P中某处出现过 S在P中某处出现过为避免重复工作 此情况不予考虑 最优子串S Ui P Q S的开始位置不能太迟 这里用到了字符串分解的定义 最优子串S b 最末循环节包含Ui 1 Ui Ui 1 P Q 最末循环节 红色和绿色线段标示了相同的子串根据定义 Ui 1 红色线段矛盾 情况b不存在 S的循环节不能太长 这里再次用到了字符串分解的定义 Ui 1 最优子串S c S位于Ui 1之前的子串 循环周期L Ui Ui 1 P Q 最末循环周期 红色和绿色线段标示了相同子串根据定义 Ui 1 红色线段矛盾 情况c也不存在 S的开始位置不能太早 这里又一次用到了字符串分解的定义 重要结论1 1 S的开始位置早于Ui且最末循环节没有将Ui 1包含在内 故L Ui 1 Ui 2 S位于Ui 1之前的子串 循环周期L 故 S 2 Ui 1 Ui 开始位置 Ui 1 P Q 最优子串S Ui Ui 循环周期L Ui 1 最末循环节 重要结论1 Ui 1 V U 进一步分类因为 S 2 故下列两种情况S必居其一 情况1 S在V中的长度 L情况2 S在U中的长度 L 最优子串S Ui 实际就是 的一个完整循环节 U 1 L 这个结论很重要 找到循环节了 V U 最优子串S 1 尽量向右扩展 三 循环节扩展和长度判定 完整循环节 2 尽量向左扩展 3 如果扩展以后的 S 2L 那么S是最优子串 U 1 L 实际就是 的一个完整循环节 找到循环节了 BBAABABAABABB 举例 V U 寻找循环周期为5的最优子串 完整循环节 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 举例 BBAABABAABABB V U 结束位置 寻找循环周期为5的最优子串 完整循环节 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 结束位置 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 结束位置 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 结束位置 举例 BBAABABAABABB V U 寻找循环周期为5的最优子串 完整循环节 结束位置 举例 BBAABABAABABB V U 开始位置 长度判定 S 11 2 5 寻找循环周期为5的最优子串 结束位置 S是合法最优子串 完整循环节 V U 完整循环节 辅助函数和重要结论2 BBAABABAABABB LsL U与U 1 L U 的最长公共前缀 LpL V与V U 1 L 的最长公共后缀 当且仅当 LsL LpL L时 存在唯一的周期为L的最优子串LsL U 1 L LpL AB 向右扩展 BAAB 向左扩展 长度判定 BAAB AB 长度判定 S 11 2 5 S是合法最优子串 使用一次 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 算法基本框架回顾和完善 字符串分解answer 0 令V 长度为 Ui 2 Ui 1 的P的后缀U Ui Fori 2tomdoEndFor 针对情况1 S在V中的长度 L End情况1 1 求出函数Ls和函数Lp的值 针对情况2 S在U中的长度 LEnd情况2 2 ForL 1to Ui 1 Ui 1do 输出answer If LsL LpL L Then用L更新answer的值 算