论文--多串匹配算法及其启示

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

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

2、到理论高度。23[目录]§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单词前缀树的时间复杂度§4.4主过程§4.5时空复杂度§4.6该算法的一些扩展§5后缀树和McCreight算法§5.1数据结构§5.2一些定义§5.3建立后缀

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总结23[正文]§1问题的提出§1.1问题描述所谓多串匹配，就是给定一些模式串，在一段文章（只出现小写a到z这26个字母）中，找出第一个出现的任意一个模式串的位置。具体来说就是：给定m个长度分别为L1、L2……Lm的模式串数组P1[1..L1]、P2[1..L2]……Pm[1..Lm]，

4、假设正文为一个长度为n的数组T[1..n]，限定。我们要找到一个最小的整数，满足使得都有注：如模式串为cdefg与efg，正文为abcdefgh时，会造成匹配目标的不明确，因此我们一般将“求所有模式串的所有出现位置”这一任务模糊，转而求“第一个”（不过接下来将介绍的算法，可以在不改变复杂度的情况下完全接受此任务）。含逻辑关键字的搜索引擎是这个问题的实际应用。医学家们在DNA序列中，搜索可能为变异的几种模式，也是这类问题的典型。因此用有效算法解决该问题能大大提高各行各业的工作效率！§1.2最初想法Foriß1tonDoForjß1tomDoIfi+Lj-1<=n

5、ThenIfT[i..i+Lj-1]=Pj[1..Lj]Then输出位置i，并退出循环最朴素的想法是：该算法从小到大枚举每一个位置，并且进行检查。最坏情况下时间复杂度为。Foriß1tomDoXißPi在T中第一次出现的位置，如果没出现返回∞writemin(X)另一个有效的优化是：其中Pi在T中第一次出现的位置，可以通过kmp算法（下一章将提到），在内完成。因此总复杂度为。可惜这两种方法面对我们即将解决的数据量，是力不从心的，我们应该努力想出一种线性,或者更优秀的算法。为此，我们要先介绍一个预备算法——kmp23（Knuth-Morris-Pratt）单串匹

6、配算法，和一个预备数据结构——单词前缀树。§2Knuth-Morris-Pratt算法该算法为D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，被称作“克努特——莫里斯——普拉特操作”，简称kmp算法。§2.1定义给定一个长度为m的模式串P[1..m]，和一个长度为n的正文T[1..n]，找到所有的整数，满足：对于都有。§2.2模式串的前缀函数（PrefixFunction）图1对有前缀函数，如图1：该函数可以通过如下程序段在数组中完成预处理：kß0π[1]ß0Foriß2tomdoWhilek>0andP[k+1]≠P[i]Dokßπ[

7、k];IfP[k+1]=P[i]Thenkßk+1;π[i]ßk;EndFor23因为k的增加值最多为m-1（最多进行m-1个“kßk+1”）,所以“kßπ[k]”的执行数量不会超过m-1次。该程序段的复杂度为。§2.3kmp主算法因为前缀函数记录了模式串自身的位移匹配信息，所以在串匹配算法中，遇到了不匹配的字符，就可以根据前缀函数进行适当的调整，而不需要进行重新的比对。图2如图2，当我们在串中匹配到了“”的时候，可以根据π[5]=3，将模式串右移5-3=2格，再接着比对（如果还不匹配，再根据π进行右移……）。类似于计算前缀数组的方法，我们也不难写出这段主算法

8、的伪代码：qß0Foriß1tonDo