资源描述：
《《论文_并行计算-实验指导-实验02串匹配(定稿)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验2串匹配1、KMP串匹配算法11.1KMP串匹配及其串行算法11.2KMP串匹配的并行算法52、随机串匹配算法92.1随机串匹配及其串行算法92.2随机串匹配的并行算法113、近似串匹配算法123.1近似串匹配及其串行算法123.2近似串匹配的并行算法17小结19参考文献20串匹配(StringMatching)问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题它在文字编辑处理、图像处理、文献检索、自然语言识别、牛物学等领域有着广泛的应用。而且，宙匹配是这些应用中最耗时的核心问题,好的串匹配算法能显
2、著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值和实际意义。串匹配问题实际上就是-•种模式匹配问题,即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(KeywordMatching).所谓关键词匹配,是指给定一个长为n的文木串T[l,n]和氏为m的模式串P[l,m]f找出文木串T中与模式串所有梢确匹配的子串的起始位置。串匹配问题包扌舌精确串匹配(PerfectStringMatching)、随机申匹配(RandomizedStringMatching)和近似串匹配(
3、ApproximateStringMatching)。另外还肓多维串匹配(MuitidimensionalStringMatching)和硬件串匹配(HardwareStringMatching)等。木章中分别介绍改进的KMP串匹配算法,采川散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法,以及它们的MP1编程实现。1、KMP串匹配算法1.1KMP串匹配及其串行算法KMP算法首先是由D.E.Knuth.J.H.Morris以及V.R.Pmtt分别设计出來的,所以该算法被命名为KMP算法。KMP串匹配算的基本思想是:
4、对给岀的的文本串T[1,叩与模式串P[l,m]f假设在模式匹配的进程中,执行T[订和P[j]的匹配检查。若T[订二P[j],则继续检查T[i+1]和P[j+1]是否匹配。若T[i]HP[j],则分成两种情况:若j二1,则模式串右移一位,检査T[i+1]和P[l]是否匹配;若lgm,则模式串右移j—next(j)位,检查T[i]和P[next(j)]是否匹配(其中next是根据模式串P[l,m]的本身局部匹配的信息构造而成的)。重复此过程ft到或i=n结束。1.修改的KMP算法在原算法基础上很多学者作了一些改进工作,其中之
5、一就是重新定义了KMP算法中的next函数,即求门ext函数时不但要求P[l,next(j)—l]=P[j—(next(j)—1),jT],而且要求P[next(j)]HP[j],记修改后的next函数为newnext。在模式串字符觅复高的情况下修改的KMP算法比传统KHP算法更加有效。算法14.1修改的KMP串匹配算法输入：文木串T[l,n]和模式串P[l,m]输出:是否存在匹配位置proceduremodeifedKMPBegin(1)i=lfj=l(2)whileiWndo(2.1)whilejHOandP[j]H
6、T[i]doj=newnext[j]endwhile(2.2)ifJ=mthenreturntrueelsej二j+l,i=i+lendifendwhile(1)returnfalseEnd算法14.2next函数和nownoxt函数的计算算法输入:模式串P[l,m]输出:next[1,m+1]和newnext[l,m]procedurenextBegin(1)next[l]=0(2)j=2(3)whilejWindo(3.1)i=next[j-l](3.2)whileiHOandP[i]^P[j~l]doi=next[
7、i]endwhile(3.3)next[j]=i+l(3.4)j二j+1endwhileEndprocedurenownextBegin(1)newnext(1)=0(2)j=2(3)whilejW/ndo(3.1)i=next(j)(3.2)ifi=0orP[j]HP[i+l]thennewnext[J]=ielsenewnext[j]=newnext[i]endif(3.3)j=j+lendwhileEnd1.改进的KE算法易知算法14.1的时间复杂度为0(n),算法14.2的时间复杂度为0(m)o算法14.1中所给
8、出的KMP算法只能找到第一个匹配位置,实际应用中往往需要找出所有的匹配位置。下血给出改进后的算法14.3便解决了这一问题。算法14.3改进KMP串匹配算法输入：文木串T[l,n]和模式串P[l,m]输出:匹配结果match[l,n]procedureimprovedKMPBegin(1)i=l,j=l(2)while
