并行计算实验指导免费版[精编]

《并行计算实验指导免费版[精编]》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大家支持免费共享2串匹配串匹配(StringMatching)问题是计算机科学屮的一个基木问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、主物学等领域有着广泛的应用。而口，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显苦地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。串匹配问题实际上就是一种模式匹配问题，即在给定的文木串屮找出与模式串匹配的子串的起始位置。最基木的串匹配问题是关键词匹配(KeywordMatching)。所谓关键词匹配,是指给定一个长为n的文本串T[l,n]和长为m的模

2、式串P[l,m],找出文本串T中与模式串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配(PerfectStringMatching)>随机串匹配(RandomizedStringMatching)和近似串匹配(ApproximateStringMatching)«另外还有多维串匹配(MultidimensionalStringMatching)和硬件串匹配(HardwareStringMatching)等。木章屮分别介绍改进的KMP串匹配算法，采用散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法，以及它们的MPI编程实现。2.1KMP串匹配算法1!2.1.1K

3、MP串匹配及其串行算法KMP算法首先是由D.E.Knuth、J.H.Morris以及V.R.Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP$匹配算的基本思想是：对给出的的文本串TL1,n]•模式串PL1,m],假设在模式匹配的进程中,执行7Ti]和P[j]的匹配检查。若Hi]二P[j],则继续检查71i+l]和P[j+l]是否匹配。若则分成两种情况：若j=l,则模式串右移一位,检查71沖]和P[l]是否匹配;若1vjWm,则模式串右移j-next①位，检查加]和P[next(j)]是否匹配(英中next是根据模式串P[l,m]的木身局部匹祀的信息构造而成的)

4、。重复此过程直到j=m或i=n结束。1.修改的KMP算法在原算法基础上很多学者作了一些改进工作，其中之一就是重新定义了KMP算法中的next函数,即求next函数时不但要求P[1,next(j)—l]=P[j—(next(j)—1),j-1],而且要求P[next(j)]HP[j],记修改后的next函数为newnexto在模式串字符重复高的悄况下修改的KMP算法比传统KMP算法更加冇效。算法14.1修改的KMP串匹配算法输入：文本串711,山和模式串P[l,mJ输出：是否存在匹配位置proceduremodeifed_KMPBegin(1)i=l,j=l(2)whilei

5、Wndo(1.1)vvhilej^0andP[j]HT[i]doj=newnext[j]endwhile(1.2)ifj=mthenreturntrueelsej=j+l,i=i+lendifendwhile(2)returnfalseEnd算法14.2next函数和newnext函数的计算算法输入：模式$P[1,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]en

6、dwhile(3.3)next[j]=i+l(3.4)j=j+lendwhileEndprocedurenewnextBegin(1)newnext(1)=0⑵j=2(3)whilej^mdo(3.1)i=next(j)(3.2)ifi=0orP[j]HP[i+l]thennewnext[j]=ielsencwncxt[j]=ncwncxt[i]endif(3.3)j=j+lendwhileEnd1.改进的KMP算法易知算法14」的时间复杂度为O(n),算法14.2的时间复杂度为O(m)。算法14」中所给出的KMP算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配

7、位置。下面给出改进后的算法14.3便解决了这一问题。算法14.3改进KMP串匹配算法输入：文本$711,n]和模式串F[l,m]输出：匹配结果match[l,n]procedureimproved_KMPBegin(1)i=l,j=l(2)whileiWndo(2.1)whilejHOandP[j]HT[i]doj=newnext[jjendwhile(2.2)ifj=mthenmatch[i-(m-l)]=lj=next[m+l]i=i+lelsei=i+lj=j+lendifendwhile(3)max_pre