寻找大重复子串.pptx

求最大重复子串

江苏金陵中学林希德

题目字符串W由大写字母组成，W中包含一些连续出现两次的相同子串，称之为重复子串。重复子串的大小决定于循环节的长度。

W=“BBAABABAABABB”ABAABA举例BB循环节长度为3循环节长度为1

请你求出最大重复子串的循环节长度。题目字符串W由大写字母组成，W中包含一些连续出现两次的相同子串，称之为重复子串。重复子串的大小决定于循环节的长度。

数据规模n=|w|=100000O(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-1PQUi-2U1字符串W将W分解成W=U1+U2+U3+……+Um的形式，其中Ui定义如下：W=P+QP=U1+U2+……+Ui-1Q1只要字符串x的开始位置在P内，就认为x在P中出现过！

ABAABABAABABB举例PQA

ABAABABAABAAB举例PQB

ABAABABAABAAB举例PQAA

ABAABABAABAAB举例PQABAABA

ABAABABAABAAB举例PQBAABABAABA

ABAABABAABAAB举例PQ

ABAABABAABAAB举例字符串分解过程借助“后缀树”算法实现ABAB

怎样利用字符串分解的特殊定义找到最优子串S的一个完整循环节呢？S的循环节能有多长呢?分类讨论。二、寻找完整循环节问题：S的开始位置在何处呢？解决方法：假设S的结束位置在固定片断Ui内一定要记住：整数i是个已知常量！！

S的开始位置也在Ui内.Ui在P中某处出现过?S在P中某处出现过为避免重复工作，此情况不予考虑！最优子串SUiPQS的开始位置不能太迟这里用到了字符串分解的定义

最优子串Sb.最末循环节包含Ui-1UiUi-1PQ最末循环节红色和绿色线段标示了相同的子串根据定义，|Ui-1|=红色线段矛盾，情况b不存在。S的循环节不能太长这里再次用到了字符串分解的定义Ui-1

最优子串Sc.|S位于Ui-1之前的子串|=循环周期LUiUi-1PQ最末循环周期红色和绿色线段标示了相同子串根据定义，|Ui-1|=红色线段矛盾，情况c也不存在。S的开始位置不能太早这里又一次用到了字符串分解的定义

重要结论11.S的开始位置早于Ui且最末循环节没有将Ui-1包含在内，故L|Ui-1+Ui|2.|S位于Ui-1之前的子串|循环周期L，故|S|2|Ui-1+Ui|开始位置Ui-1PQ最优子串SUiUi循环周期LUi-1最末循环节

重要结论1Ui-1VU进一步分类因为|S|=2Ｌ，故下列两种情况S必居其一：情况1.S在V中的长度=L情况2.S在U中的长度=L最优子串SUi实际就是Ｓ的一个完整循环节U(1,L)这个结论很重要！！找到循环节了!!!

VU最优子串S1、尽量向右扩展三、循环节扩展和长度判定完整循环节2、尽量向左扩展3、如果扩展以后的|S|=2L