求最大重复子串求最大重复子串江苏金陵中学林希江苏金陵中学林希德德题目题目字符串W由大写字母组成，W中包含一些连续出现两次的相同子串，称之为重复子串。重复子串的大小决定于循环节的长度。W=“BBAABABAABABB”ABAABA举例举例<=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-1PQUi-2U1字符串W将W分解成W=U1+U2+U3+……+Um的形式，其中Ui定义如下：W=P+QP=U1+U2+……+Ui-1Q1只要字符串x的开始位置在P内，就认为x在P中出现过！ABAABABAABABB举例举例PQAABAABABAABAAB举例举例PQBABAABABAABAAB举例举例PQAAABAABABAABAAB举例举例PQABAABAABAABABAABAAB举例举例PQBAABABAABAABAABABAABAAB举例举例PQABAABABAABAAB举例举例字符串分解过程借助“后缀树”算法实现ABAB怎样利用字符串分解的特殊定义找到怎样利用字符串分解的特殊定义找到最优子串最优子串SS的一个完整循环节呢？的一个完整循环节呢？S的循环节能有多长呢?分类讨论。二、寻找完整循环节二、寻找完整循环节问题：S的开始位置在何处呢？解决方法：假设假设SS的结束位置在固定片断的结束位置在固定片断UUii内内一定要记住：整数i是个已知常量！！a.S的开始位置也在Ui内.Ui在P中某处出现过S在P中某处出现过为避免重复工作，此情况不予考虑！最优子串SUiPQSS的开始位置不能太迟的开始位置不能太迟这里用到了字符串分解的定义最优子串Sb.最末循环节包含Ui-1UiUi-1PQ最末循环节红色和绿色线段标示了相同的子串根据定义，|Ui-1|>=红色线段矛盾，情况b不存在。SS的循环节不能太长的循环节不能太长这里再次用到了字符串分解的定义Ui-1最优子串Sc.|S位于Ui-1之前的子串|>=循环周期LUiUi-1PQ最末循环周期红色和绿色线段标示了相同子串根据定义，|Ui-1|>=红色线段矛盾，情况c也不存在。SS的开始位置不能太早的开始位置不能太早这里又一次用到了字符串分解的定义重要结论重要结论111.S的开始位置早于Ui且最末循环节没有将Ui-1包含在内，故L<|Ui-1+Ui|2.|S位于Ui-1之前的子串|<循环周期L，故|S|<2|Ui-1+Ui|开始位置Ui-1PQ最优子串SUiUi循环周期LUi-1最末循环节重要结论重要结论11Ui-1VU进一步分类因为|S|>=2Ｌ，故下列两种情况S必居其一：情况1.S在V中的长度>=L情况2.S在U中的长度>=L最优子串SUi实际就是Ｓ的一个完整循环节U(1,L)这个结论很重要！！找到循环节了!!!VU最优子串S1、尽量向右扩展三、循环节扩展和长度判定三、循环节扩展和长度判定完整循环节2、尽量向左扩展3、如果扩展以后的|S|>=2L，那么S是最优子串。U(1,L)实际就是Ｓ的一个完整循环节找到循环节了!!!BBAABABAABABB举例举例VU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU结束位置寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例举例BBAABABAABABBVU...
