并行计算-实验指导-实验02串匹配

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

1、实验2串匹配1、KMP串匹配算法1」KMP串匹配及其串行算法11.2KMP串匹配的并行算法52、随机串匹配算法92.1随机串匹配及其串行算法92.2随机串匹配的并行算法113、近似串匹配算法123」近似串匹配及其串行算法123.2近似串匹配的并行算法17小结20参考文献20串匹配(StringMatching)问题是计算机科学中的一个基本问题，也是复杂性理论屮研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而fl,串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用

2、的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。串匹配问题实际上就是-•种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(KeywordMatching)。所谓关键词匹配，是指给定一个长为n的文本串T[l,n]利氏为m的模式串P[l,m],找出文本串T中与模式串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配(PerfectStringMatching)、随机串匹配(RandomizedStringMatching)和近似串匹配(ApproximateStr

3、ingMatching)o另外还有多维串匹配(MultidimensionalStringMatching)和硬件串匹配(HardwareStringMatching)等。本章中分别介绍改进的KMP串匹配算法，采用散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法，以及它们的MPI编程实现。1、KMP串匹配算法1.1KMP串匹配及其串行算法KMP算法首先是由D.E.Knuth、J.ILMorris以及V.R.Pratt分别设计出来的,所以该算法被命名为KMP算法。KMP串匹配算的基本思想是:对给出的的文本串711,n]与模式串/<

4、1,m],假设在模式匹配的进程中,执行T[i]和円j]的匹配检查。若Tti]才[j],则继续检査7[i+l]和円j+1]是否匹配。若Tti]HP[j]，则分成两种情况:若j二1,则模式串右移一位，检查7[i+l]和Ptl]是否匹配;若1

5、xt函数时不但要求P[l,next(j)—1]二P[j—(next(j)—1),j-1],而且要求円next(j)]HP[j],记修改后的next函数为newnexto在模式串字符重复高的情况下修改的KMP算法比传统KMP算法更加冇效。算法14.1修改的KMP串匹配算法输入:文本串7tl,n]和模式串P[l,m]输出：是否存在匹配位置proceduremodeifed_KMPBegin(1)i=l,j=l(2)wh订eiWndo(2.1)whilejHOandP[j]HT[i]doj=newnext[j]endwhile(2.2)if

6、j=mthenreturntrueelsej二j+l,i二i+1endifendwhile(3)returnfalseEnd算法14.2next函数和newnext函数的计算算法输入：模式串Mbm]输出：next[1,m+1]和newnext[1,m]procedurenextBegin(1)next[l]=0(2)j=2(3)wh订ejWmdo(3.1)i二next[j—1](3.2)whileiHOandP[i]HP[jT]doi二next[i]endwhile(3.3)next[j]=i+l(3.4)j二j+1endwhileE

7、ndprocedurenewnextBegin(1)newnext(1)=0⑵j=2(3)whi.lejWmdo(3.1)i=next(j)(3.2)ifi=0orP[j]HP[i+l]thennewncxt[j]=ielsenewnext[j]二newnext[i]endif(3.3)j=j+lendwhileEnd1.改进的KMP算法易知算法14.1的时间复杂度为0(n),算法14.2的时间复杂度为0(m)0算法14.1中所给出的KMP算法只能找到第一个匹配位置，实际应用屮往往需要找出所有的匹配位置。下面给出改进后的算法14.3便

8、解决了这一问题。算法14.3改进KMP串匹配算法输入：文木串711,n]和模式串P[l,m]输出：匹配结果match[1,n]procedureimproved_KMPBegin(1)i=l,j=l(2)whi.leiW