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

多串匹配算法及其启示[关键字]模式串单词前缀树后缀树串匹配[摘要]字符串处理在实际应用中具有重要地位,其看似简单,但随着研究的深入,各类思想精华涌现其中,难度也变得深不可测。因此信息学竞赛中常以字符串处理为题,锻炼选手的创新能力。本文第一章提出问题并进行朴素的分析,第二、三、五章分别介绍三个辅助算法:KMP模式匹配算法、自创的单词前缀树算法,以及后缀树算法。另外基于KMP算法的核心思想,在第四章中,面向“多串匹配”问题提出一个线性算法。但本文并没有满足于线性时间复杂度,接着在第六章提出了平均性能更好的算法。最后第七章对算法的构思进行了剖析,并将这种思想方法上升到理论高度。[目录]§1问题的提出§§§2Knuth-Morris-Pratt算法§§(PrefixFunction)§§3单词前缀树§(Trie)的定义§§§§4主算法一(线性算法)§§§§§§§reight算法§§§(初步)§§§6主算法二(平均性能更好的算法)§§§§§§§7启示和总结§§§[正文]§1问题的提出§,就是给定一些模式串,在一段文章(只出现小写a到z这26个字母)中,找出第一个出现的任意一个模式串的位置。具体来说就是:给定m个长度分别为L1、L2……Lm的模式串数组P1[1..L1]、P2[1..L2]……Pm[1..Lm],假设正文为一个长度为n的数组T[1..n],限定。我们要找到一个最小的整数,满足使得都有注:如模式串为cdefg与efg,正文为abcdefgh时,会造成匹配目标的不明确,因此我们一般将“求所有模式串的所有出现位置”这一任务模糊,转而求“第一个”(不过接下来将介绍的算法,可以在不改变复杂度的情况下完全接受此任务)。含逻辑关键字的搜索引擎是这个问题的实际应用。医学家们在DNA序列中,搜索可能为变异的几种模式,也是这类问题的典型。因此用有效算法解决该问题能大大提高各行各业的工作效率!§ß1tonDo Forjß1tomDoIfi+Lj-1<=nThen IfT[i..i+Lj-1]=Pj[1..Lj]Then 输出位置i,并退出循环最朴素的想法是:该算法从小到大枚举每一个位置,并且进行检查。最坏情况下时间复杂度为。Foriß1tomDo XißPi在T中第一次出现的位置,如果没出现返回∞writemin(X)另一个有效的优化是:其中Pi在T中第一次出现的位置,可以通过kmp算法(下一章将提到),在内完成。因此总复杂度为。可惜这两种方法面对我们即将解决的数据量,是力不从心的,我们应该努力想出一种线性,或者更优秀的算法。为此,我们要先介绍一个预备算法——kmp(Knuth-Morris-Pratt)单串匹配算法,和一个预备数据结构——单词前缀树。§2Knuth-Morris-、,被称作“克努特——莫里斯——普拉特操作”,简称kmp算法。§[1..m],和一个长度为n的正文T[1..n],找到所有的整数,满足:对于都有。§(PrefixFunction)图1对有前缀函数,如图1:该函数可以通过如下程序段在数组中完成预处理:kß0π[1]ß0Foriß2tomdo Whilek>0andP[k+1]≠P[i]Dokßπ[k]; IfP[k+1]=P[i]Thenkßk+1; π[i]ßk;EndFor因为k的增加值最多为m-1(最多进行m-1个“kßk+1”),所以“kßπ[k]”的执行数量不会超过m-1次。该程序段的复杂度为。§,所以在串匹配算法中,遇到了不匹配的字符,就可以根据前缀函数进行适当的调整,而不需要进行重新的比对。图2如图2,当我们在串中匹配到了“”的时候,可以根据π[5]=3,将模式串右移5-3=2格,再接着比对(如果还不匹配,再根据π进行右移……)。类似于计算前缀数组的方法,我们也不难写出这段主算法的伪代码:qß0Foriß1tonDo Whileq>0