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

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

ID:37806804

大小:819.50 KB

页数:38页

时间:2019-05-31

算法合集之《寻找最大重复子串》_第1页
算法合集之《寻找最大重复子串》_第2页
算法合集之《寻找最大重复子串》_第3页
算法合集之《寻找最大重复子串》_第4页
算法合集之《寻找最大重复子串》_第5页
资源描述:

《算法合集之《寻找最大重复子串》》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

2、w

3、<=100000O(n2)O(nlg2n)O(n)后缀树两个辅助算法O(n)KMP模式匹配O(n+m)为方便表达,使用表示开始于位置u结束于位

4、置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、判断扩展以后的S是否长度>=2L如果是,则认为找到了一个循环周

7、期为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举例PQBAABABAABAABAABABAA

8、BAAB举例PQABAABABAABAAB举例字符串分解过程借助“后缀树”算法实现ABAB怎样利用字符串分解的特殊定义找到最优子串S的一个完整循环节呢?S的循环节能有多长呢?分类讨论。二、寻找完整循环节问题:S的开始位置在何处呢?解决方法:假设S的结束位置在固定片断Ui内一定要记住:整数i是个已知常量!!S的开始位置也在Ui内.Ui在P中某处出现过S在P中某处出现过为避免重复工作,此情况不予考虑!最优子串SUiPQS的开始位置不能太迟这里用到了字符串分解的定义最优子串Sb.最末循环节包含Ui-1UiUi-1PQ最末循环节红色和绿色

9、线段标示了相同的子串根据定义,

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且最末循环节没有将Ui-1包含在内,故L<

16、Ui-1+Ui

17、2.

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

19、<循环周期L,故

20、S

21、<2

22、Ui-1+Ui

23、开始位置Ui-1P

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

25、S

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

27、S

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

29、ABABAABABBVU寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU结束位置寻找循环周期为5的最优子串完整循环节举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例BBAABAB

30、AABABBVU开始位置长度判定:

31、S

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

33、U

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。