资源描述：
《并行计算实验指导(1)版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、大家支持免费共享2串匹配串匹配(StringMatching)问题是计算机科学屮的一个基本问题，也是复杂性理论中研究的最广泛的问题么一。它在文字编辑处理、图像处理、文献检索、白然语言识别、生物学等领域有着广泛的应川。而H,串匹配是这些应川屮最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的申匹配算法具有重要的理论价值和实际意义。串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(KeywordMatching)。所谓关键词匹配,是指给定一个长为n的文本串71bn]和长为m的模式串P[l,m],
2、找出文本串T中与模式串所有精确匹配的子串的起始位置。申匹配问题包括精确串匹配(PcifcclSiringMatching)>随机串匹配(RandomizedStringMalching)和近似串匹配(ApproximateStringMatching)。另外还有多维串匹配(MultidimensionalStringMatching)和硬件串匹配(HaidwareStringMatching)等。本章中分别介绍改进的KMP串匹配算法，采用散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法，以及它们的MPI编程实现。2.1KMP串匹配算法2.1.1KMP串匹配及其串行算法KMP算法首先是
3、由D.E.Knuth>J.H.Morris以及V.R.Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP串匹配算的基木思想是：对给出的的文木串T[l,n]与模式串P[l,m],假设在模式匹配的进程中,执行71i]和啲匹配检查。若T[i]=P[j]»则继续检查T[i+1]和P[j+1]是否匹配。若则分成两种情况：若j=I,则模式串右移一位,检查W+1J和P[l]是否匹配;若1vjWm,则模式串右移j-next①位,检查HijfilP[next(j)J是否匹配(其中next是根据模式串P[l,m]的本身局部匹配的信息构造而成的)。重复此过程直到j=m或i=n结束。修改的KMP算法在
4、原算法基础上很多学者作了一些改进工作，其中Z—就是重新定义了KMP算法中的next函数，即求next函数时不但要求P[l,next(j)—l]=P[j—(next(j)—1),j-1],而且要求P[next(j)]记修改后的next函数为newnexto在模式串字符重复高的情况卜修改的KMP算法比传统KMP算法更加有效。算法14・1修改的KMP串匹配算法输入：文本串7[1,n]和模式串P[l,m]输出：是否存在匹配位置proceduremodeifed_KMPBegini=l,j=lwhilei^ndowhilejH0andP[j]HT[i]doj=newnext[j]endwhileif
5、j=mthenreturntrueelsej=j+l,i=i+lendifendwhilereturnfalseEnd算法14.2next函数和newnext函数的计算算法输入：模式串P[l，m]输出：next[l,m+1]和newnext[l,m]procedurenextBegin(1)next[l]=0⑵j=2(3)whilej^mdo(3.1)i=next[j-l](3.2)whileiHOandP[i]HP[j・l]doi=next[i]endwhile(3.3)next
6、j]=i+l(3.4)j=j+lendwhileEndprocedurenewnextBeginnewnex
7、t(l)=O⑵j=2(3)whilej^mdo(3.1)i=next(j)(3.2)ifi=0orP[j]HP[i+l]thennewnextfj]=ielsenewnext[j]=newnext[i]endif(3.1)j=j+lendwhileEnd改进的KMP算法易知算法14」的时间复杂度为O(n),算法14.2的时间复杂度为O(m)。算法14」中所给出的KMP算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。下面给出改进后的算法14.3便解决了这一问题。算法14・3改进KMP串匹配算法输入：文本串T[l,n]和模式串P[l,m]输出：匹配结果matchfl,n]pr
8、ocedureimproved_KMPBegini=l,j=lwhilei^ndowhilejHOandP[j]HT[i]doj=newnext[j]endwhileifj=mthenmatch[i-(m-1)]=1j=next[m+l]i=i+lelsei=i+lj=j+lendifendwhilemax_prefix_len=j-lEnd算法14.4next函数和newnext函数的计算算法输入：模式串P[l,m]输
