资源描述：
《寻找最大重复子串》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、寻找最大重复子串【关键字】后缀树KMP推广算法最优子串【摘要】关于字符串处理，无论是国内的个大竞赛还是中文的经典宝书，都相对较少涉及。曾见各位高手在信息学论坛上就某前辈提出的此类问题讨论得热火朝天，于是我决心翻阅多方资料仔细研究，仅望对大家发表高见起抛砖引玉的小作用。本文第一章给出了问题的详细描述和我对该问题的拙见，第二、三章简述了字符串处理的两个常用算法——后缀树和KMP，第四章阐明了寻找最大重复子串的主算法。[目录]一问题提出和初步认识1.1问题描述1.2初步分析二后缀树2.1后缀树的定义2.2后缀树的构建2.3后缀链接2.4性能分析三模式匹配3.1朴素模式匹配3.2KMP模式
2、匹配3.3前缀函数3.4性能分析3.5KMP推广算法四主算法4.1问题转化4.2字符串分解4.3范围限定4.4找到循环节4.5辅助函数4.6性能分析五论文小结16[正文]一、问题提出和初步分析1.1章节定义一：对于字符串S，如果存在正整数p使得1x
3、S
4、-p：Sx=Sx+p。那么称p是S的循环周期(Period)，e=
5、S
6、/p是S的指数(Power)，任何长度为p的S的子串都是S的一个循环节(Repetend)，特别的，当e2时，S是个大小为p的重复字符串(RepetitionorP-powerword)。问题描述：给出一个由大写字母组成的字符串W，W长度为1n105，请你在W的
7、所有子串中找出循环周期最长的那个重复字符串（FindingMaximalRepetition），即最大重复子串。1.2章节定义二：为方便表达，我们用符号W(u,v)表示开始于位置u结束于位置v的W的子串。初步分析：一个O(n2)的算法是乍一看最直观的收获。我们可以首先从n到1枚举循环周期p，然后针对p从位置1到n搜索重复子串，一旦找到立即输出并退出循环，如下：Forp=nà1doFori=1àndoIfi>p并且Wi=Wi-pthenGi=Max(Gi-1+1，1)ElseGi=0EndifIfGi=pthen输出W(i-2p+1,i)；退出循环EndforEndfor这个O(n2
8、)的算法简单易编，但速度较慢。那么，怎样让复杂度从O(n2)降到O(n)呢？为说清楚这个线性算法，我们不得不先介绍一种关于字符串处理的数据结构——后缀树，还有就是模式匹配的KMP。16二、后缀树2.1章节后缀树定义：令W=W+'$'，这样W的最后一个字符从未在前面的任何一个位置上出现过。添置'$'的目的，将在下一小节中予以说明。后缀树其实就是一棵检索树(Trie)，和普通检索树一样我们不断往树中插入字符串和添置顶点，只不过，后缀树还有一些特殊的性质：ⅰ）我们从大到小依次往树中插入W的后缀，这其实是后缀树的名称由来，也是它的构建过程。ⅱ）树上每条边E(u,v)有两个参数г和，记为E(
9、u,v)=(г,），代表子串W(г,)。ⅲ）树上每个节点均有26个儿子，代表26个大写字母。如果父亲节点u的第1个儿子是节点a，那么E(u,a)上的子串一定以字母A开头；如果第2个儿子是节点b，那么E(u,b)上的子串一定以字母B开头……以此类推。定义三：如果从根Root到节点x途径若干条边，将这些边上的子串顺次连接得到字符串Sx，那么称Sx是x的对应子串，x是Sx的对应节点。易知，“节点à对应子串”和“字符串à对应节点”都是一一映射的关系。ⅳ）后缀树有n个叶子节点Leaf1、Leaf2……Leafn，Leafi的对应子串实际就是W的后缀W(i,n)。这一点通过性质ⅰ）就可以得到，
10、这里无非明确一下。2.2章节定义四：Headi是W(i,n)和W(j,n)的最长公共前缀，其中j是小于i的任意正整数，Taili使得Headi+Taili=W(i,n)。定义五：只要子串S=W(u,v)满足ux，我们就说S在范围x内出现过。Headi其实就是在范围i-1内出现过的W(i,n)的最长前缀。初始化后缀树为只有根结点的树Fori=1àndo找到Headi的对应节点hi；增加叶节点Leafi，使得E(hi,Leafi)=(
11、Headi
12、+1,n)；Endfor后缀树的构建：16举例一：下面让我们来看看字符串W=“AGATAGAG$”的后缀树被逐步构建的具体例子，其中黑色圆圈
13、是叶节点，圆括号内的是边参数(г,）：16增加Leafi只是O(1)的工作，关键问题是如何找到Headi的对应节点hi。最直观也是最野蛮的方法是从根节点开始对W(i,n)实行逐个字符地扫描：hi=Find(Root，W(i,n))；FunctionFind(实参：开始节点p；字符串S)：指针类型；Whiletruedoe=p的第ord(S1)-64个儿子节点；Ife不存在then返回指针p，Break；Endif逐个字符比较找出S与E(p,e)的最长公共前缀UL=
14、U
