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

《算法合集之《寻找最大重复子串》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求最大重复子串江苏金陵中学林希德题目字符串W由大写字母组成，W中包含一些连续出现两次的相同子串，称之为重复子串。重复子串的大小决定于循环节的长度。W=“BBAABABAABABB”ABAABA举例

2、w

3、<=100000O(n2)O(nlg2n)O(n)后缀树两个辅助算法O(n)KMP模式匹配O(n+m)为方便表达

4、，使用表示开始于位置u结束于位置v的W的子串W(u，v)问题的转化1、S中的字符以L为周期循环出现Si=Si+L（u<=i<=v-L）求出所有最优子串连同它们的周期定义S是循环周期为L的最优子串，仅当S满足：2、

5、S

6、>=2L，即S至少包括两个完整循环节。3、S不能向左扩展，即u=1或者W(u-1,v)不满足条件14、S不能向右扩展，即v=n或者W(u,v+1)不满足条件1最大重复子串必然被某个最优子串包含！！算法基本框架1、找到S的一个完整循环节2、根据循环节将S分别向左、向右扩展到不能扩展为止3、判

7、断扩展以后的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举

8、例PQABAABAABAABABAABAAB举例PQBAABABAABAABAABABAABAAB举例PQABAABABAABAAB举例字符串分解过程借助“后缀树”算法实现ABAB怎样利用字符串分解的特殊定义找到最优子串S的一个完整循环节呢？S的循环节能有多长呢?分类讨论。二、寻找完整循环节问题：S的开始位置在何处呢？解决方法：假设S的结束位置在固定片断Ui内一定要记住：整数i是个已知常量！！S的开始位置也在Ui内.Ui在P中某处出现过S在P中某处出现过为避免重复工作，此情况不予考虑！最优子串SUiP

9、QS的开始位置不能太迟这里用到了字符串分解的定义最优子串Sb.最末循环节包含Ui-1UiUi-1PQ最末循环节红色和绿色线段标示了相同的子串根据定义，

10、Ui-1

11、>=红色线段矛盾，情况b不存在。S的循环节不能太长这里再次用到了字符串分解的定义Ui-1最优子串Sc.

12、S位于Ui-1之前的子串

13、>=循环周期LUiUi-1PQ最末循环周期红色和绿色线段标示了相同子串根据定义，

14、Ui-1

15、>=红色线段矛盾，情况c也不存在。S的开始位置不能太早这里又一次用到了字符串分解的定义重要结论11.S的开始位置早于Ui且最

16、末循环节没有将Ui-1包含在内，故L<

17、Ui-1+Ui

18、2.

19、S位于Ui-1之前的子串

20、<循环周期L，故

21、S

22、<2

23、Ui-1+Ui

24、开始位置Ui-1PQ最优子串SUiUi循环周期LUi-1最末循环节重要结论1Ui-1VU进一步分类因为

25、S

26、>=2Ｌ，故下列两种情况S必居其一：情况1.S在V中的长度>=L情况2.S在U中的长度>=L最优子串SUi实际就是Ｓ的一个完整循环节U(1,L)这个结论很重要！！找到循环节了!!!VU最优子串S1、尽量向右扩展三、循环节扩展和长度判定完整循环节2、尽量向左扩展3、如果

27、扩展以后的

28、S

29、>=2L，那么S是最优子串。U(1,L)实际就是Ｓ的一个完整循环节找到循环节了!!!BBAABABAABABB举例VU寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU结束位置寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环

30、周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU开始位置长度判定：

31、S

32、=11>=2*5寻找循环周期为5的最优子串结束位置S是合法最优子串完整循环节VU完整循环节辅助函数和重要结论2BBAABABAABABBLsL=U与U(1+L，

33、U

34、)的最长公共前缀LpL=V与