国家集训队2003论文集林希德.docVIP

寻找最大重复子串 江苏金陵中学 林希德 【关键字】 后缀树 KMP推广算法 最优子串 【摘要】 关于字符串处理，无论是国内的个大竞赛还是中文的经典宝书，都相对较少涉及。曾见各位高手在信息学论坛上就某前辈提出的此类问题讨论得热火朝天，于是我决心翻阅多方资料仔细研究，仅望对大家发表高见起抛砖引玉的小作用。 本文第一章给出了问题的详细描述和我对该问题的拙见，第二、三章简述了字符串处理的两个常用算法——后缀树和KMP，第四章阐明了寻找最大重复子串的主算法。 [目录] 一 问题提出和初步认识 1.1问题描述 1.2初步分析 二 后缀树 2.1后缀树的定义 2.2后缀树的构建 2.3后缀链接 2.4性能分析 三 模式匹配 3.1朴素模式匹配 3.2 KMP模式匹配 3.3前缀函数 3.4性能分析 3.5 KMP推广算法 四 主算法 4.1问题转化 4.2字符串分解 4.3范围限定 4.4找到循环节 4.5辅助函数 4.6性能分析 五 论文小结 [正文] 一 、问题提出和初步分析 1.1章节 定义一： 对于字符串S，如果存在正整数p使得 1 x |S| - p：S x = S x + p。 那么称p是S的循环周期(Period)，e = |S| / p是S的指数(Power)，任何长度为p的S的子串都是S的一个循环节(Repetend)，特别的，当e 2时，S是个大小为p的重复字符串(Repetition or P-power word)。 问题描述： 给出一个由大写字母组成的字符串W，W长度为1 n 105，请你在W的所有子串中找出循环周期最长的那个重复字符串（Finding Maximal Repetition），即最大重复子串。 1.2章节 定义二： 为方便表达，我们用符号W(u,v)表示开始于位置u结束于位置v的W的子串。 初步分析： 一个O(n2)的算法是乍一看最直观的收获。我们可以首先从n到1枚举循环周期p，然后针对p从位置1到n有哪些信誉好的足球投注网站重复子串，一旦找到立即输出并退出循环，如下： 这个O(n2)的算法简单易编，但速度较慢。那么，怎样让复杂度从O(n2)降到O(n)呢？为说清楚这个线性算法，我们不得不先介绍一种关于字符串处理的数据结构——后缀树，还有就是模式匹配的KMP。 二、 后缀树 2.1章节 后缀树定义： 令W = W + $，这样W的最后一个字符从未在前面的任何一个位置上出现过。添置$的目的，将在下一小节中予以说明。 后缀树其实就是一棵检索树(Trie)，和普通检索树一样我们不断往树中插入字符串和添置顶点，只不过，后缀树还有一些特殊的性质： ⅰ）我们从大到小依次往树中插入W的后缀，这其实是后缀树的名称由来，也是它的构建过程。 ⅱ）树上每条边E(u,v)有两个参数г和，记为E(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)。这一点通过性质ⅰ）就可以得到，这里无非明确一下。 2.2章节 定义四： Headi是W(i,n)和W(j,n)的最长公共前缀，其中j是小于i的任意正整数，Taili使得Headi + Taili = W(i,n)。 定义五： 只要子串S = W(u,v)满足u x，我们就说S在范围x内出现过。Headi其实就是在范围i-1内出现过的W(i,n)的最长前缀。 后缀树的构建： 举例一： 下面让我们来看看字符串W = “AGATAGAG$”的后缀树被逐步构建的具体例子，其中黑色圆圈是叶节点，圆括号内的是边参数(г,）： 增加Leafi只是O(1)的工作，关键问题是如何找到Headi的对应节点hi。最直观也是最野蛮的方法是从根节点开始对W(i,n)实行逐个字符地扫描： 请看 处，或许你会担心V(L+1，|V|)可能是个无意义的空串，其实，L = |V|的情况一定不会出现。 反证法一： 如果L = |V|，那么就说明W(i,n)是某个W(j,n)（1ji）的前缀，也就是说W的末尾字符$至少出现过两次。这与刚才 处的规定违背。 故，任何增添进后缀树中的边都不是空串。 这种野蛮的扫描算法使得时间复杂度高达O(n2)，还外加一个不小的常数因子。其实，这个Find函数并不是完全