算法合集之《多串匹配算法及其启示》

《算法合集之《多串匹配算法及其启示》》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IOI2004国家集训队论文朱泽园多串匹配算法及其启示南京市外国语学校朱泽园[关键字]模式串单词前缀树后缀树串匹配[摘要]字符串处理在实际应用中具有重要地位，其看似简单，但随着研究的深入，各类思想精华涌现其中，难度也变得深不可测。因此信息学竞赛中常以字符串处理为题，锻炼选手的创新能力。本文第一章提出问题并进行朴素的分析，第二、三、五章分别介绍三个辅助算法：KMP模式匹配算法、自创的单词前缀树算法，以及后缀树算法。另外基于KMP算法的核心思想，在第四章中，面向“多串匹配”问题提出一个线性算法。但本文并没有满足于线性时间复杂度，接着在第六章

2、提出了平均性能更好的算法。最后第七章对算法的构思进行了剖析，并将这种思想方法上升到理论高度。第1页共23页IOI2004国家集训队论文朱泽园[目录]§1问题的提出§1.1问题描述§1.2最初想法§2Knuth-Morris-Pratt算法§2.1定义§2.2模式串的前缀函数（PrefixFunction）§2.3kmp主算法§3单词前缀树§3.1单词查找树（Trie）的定义§3.2单词树的建立§3.3前缀指针的定义§3.4前缀指针的生成§4主算法一（线性算法）§4.1kmp算法的启发§4.2单词前缀树的使用及附加标记§4.3单词前缀树的

3、时间复杂度§4.4主过程§4.5时空复杂度§4.6该算法的一些扩展§5后缀树和McCreight算法§5.1数据结构§5.2一些定义§5.3建立后缀树（初步）§5.4后缀链接§5.5建立后缀树§6主算法二（平均性能更好的算法）§6.1单词前缀树的使用和扩展§6.2后缀树的使用和扩展§6.3TreeA和TreeB上的两个函数§6.4主过程§6.5一个例子§6.6时间复杂度分析§7启示和总结§7.1算法分析§7.2启示§7.3总结第2页共23页IOI2004国家集训队论文朱泽园[正文]§1问题的提出§1.1问题描述所谓多串匹配，就是给定一些

4、模式串，在一段文章（只出现小写a到z这26个字母）中，找出第一个出现的任意一个模式串的位置。具体来说就是：给定m个长度分别为L1、L2……Lm的模式串数组P1[1..L1]、P2[1..L2]……Pm[1..Lm]，假设正文为一个长度为n的数组T[1..n]，限定åL£100K,m£1000,n£900K。我们要找到一个最小的整数sÎ[1,n]，满足$aÎ[1,m]使得"xÎ[1,La]都有T[s+x-1]=Pa[x]注：如模式串为cdefg与efg，正文为abcdefgh时，会造成匹配目标的不明确，因此我们一般将“求所有模式串的所有出

5、现位置”这一任务模糊，转而求“第一个”（不过接下来将介绍的算法，可以在不改变复杂度的情况下完全接受此任务）。含逻辑关键字的搜索引擎是这个问题的实际应用。医学家们在DNA序列中，搜索可能为变异的几种模式，也是这类问题的典型。因此用有效算法解决该问题能大大提高各行各业的工作效率！§1.2最初想法最朴素的想法是：Foriß1tonDoForjß1tomDoIfi+Lj-1<=nThenIfT[i..i+Lj-1]=Pj[1..Lj]Then输出位置i，并退出循环该算法从小到大枚举每一个位置，并且进行检查。最坏情况下时间复杂度为O(n×åL)。

6、另一个有效的优化是：Foriß1tomDoXißPi在T中第一次出现的位置，如果没出现返回∞writemin(X)其中Pi在T中第一次出现的位置，可以通过kmp算法（下一章将提到），在O(n+Li)内完成。因此总复杂度为O(n×m+åL)。可惜这两种方法面对我们即将解决的数据量，是力不从心的，我们应该努力想出一种线性,或者更优秀的算法。为此，我们要先介绍一个预备算法——kmp（Knuth-Morris-Pratt）单串匹配算法，和一个预备数据结构——单词前缀树。第3页共23页IOI2004国家集训队论文朱泽园§2Knuth-Morris

7、-Pratt算法该算法为D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，被称作“克努特——莫里斯——普拉特操作”，简称kmp算法。§2.1定义给定一个长度为m的模式串P[1..m]，和一个长度为n的正文T[1..n]，找到所有的整数sÎ[1,n-m+1]，满足：对于"xÎ[1,m]都有T[s+x-1]=P[x]。§2.2模式串的前缀函数（PrefixFunction）对1£i£m有前缀函数π(i)=max{j

8、P[1..j]=P[i-j+1..i]}，如错误！链接无效。：0£j£i图1该函数可以通过如下程序段在数

9、组中完成预处理：kß0π[1]ß0Foriß2tomdoWhilek>0andP[k+1]≠P[i]Dokßπ[k];IfP[k+1]=P[i]Thenkßk+1;π[i]ßk;EndFor第4页共23页I