并行计算实验指导(1)免费版

并行计算实验指导(1)免费版

ID:33650768

大小:262.00 KB

页数:22页

时间:2019-02-28

并行计算实验指导(1)免费版_第1页
并行计算实验指导(1)免费版_第2页
并行计算实验指导(1)免费版_第3页
并行计算实验指导(1)免费版_第4页
并行计算实验指导(1)免费版_第5页
资源描述:

《并行计算实验指导(1)免费版》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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

2、hing)。所谓关键词匹配,是指给定一个长为n的文本串T[1,n]和长为m的模式串P[1,m],找出文本串T中与模式串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配(PerfectStringMatching)、随机串匹配(RandomizedStringMatching)和近似串匹配(ApproximateStringMatching)。另外还有多维串匹配(MultidimensionalStringMatching)和硬件串匹配(HardwareStringMatching)等。本章中分别介绍

3、改进的KMP串匹配算法,采用散列技术的随机串匹配算法,基于过滤算法的近似串匹配算法,以及它们的MPI编程实现。2.1KMP串匹配算法2.1.1KMP串匹配及其串行算法KMP算法首先是由D.E.Knuth、J.H.Morris以及V.R.Pratt分别设计出来的,所以该算法被命名为KMP算法。KMP串匹配算的基本思想是:对给出的的文本串T[1,n]与模式串P[1,m],假设在模式匹配的进程中,执行T[i]和P[j]的匹配检查。若T[i]=P[j],则继续检查T[i+1]和P[j+1]是否匹配。若T[i]≠P

4、[j],则分成两种情况:若j=1,则模式串右移一位,检查T[i+1]和P[1]是否匹配;若1

5、t(j)]≠P[j],记修改后的next函数为newnext。在模式串字符重复高的情况下修改的KMP算法比传统KMP算法更加有效。算法14.1修改的KMP串匹配算法输入:文本串T[1,n]和模式串P[1,m]输出:是否存在匹配位置proceduremodeifed_KMP22Begin(1)i=1,j=1(2)whilei≤ndo(2.1)whilej≠0andP[j]≠T[i]doj=newnext[j]endwhile(2.2)ifj=mthenreturntrueelsej=j+1,i=i+1end

6、ifendwhile(3)returnfalseEnd算法14.2next函数和newnext函数的计算算法输入:模式串P[1,m]输出:next[1,m+1]和newnext[1,m]procedurenextBegin(1)next[1]=0(2)j=2(3)whilej≤mdo(3.1)i=next[j-1](3.2)whilei≠0andP[i]≠P[j-1]doi=next[i]endwhile(3.3)next[j]=i+1(3.4)j=j+1endwhileEndprocedurenewne

7、xtBegin(1)newnext(1)=0(2)j=2(3)whilej≤mdo(3.1)i=next(j)(3.2)ifi=0orP[j]≠P[i+1]thennewnext[j]=ielsenewnext[j]=newnext[i]endif(3.3)j=j+122endwhileEnd2.改进的KMP算法易知算法14.1的时间复杂度为O(n),算法14.2的时间复杂度为O(m)。算法14.1中所给出的KMP算法只能找到第一个匹配位置,实际应用中往往需要找出所有的匹配位置。下面给出改进后的算法14.

8、3便解决了这一问题。算法14.3改进KMP串匹配算法输入:文本串T[1,n]和模式串P[1,m]输出:匹配结果match[1,n]procedureimproved_KMPBegin(1)i=1,j=1(2)whilei≤ndo(2.1)whilej≠0andP[j]≠T[i]doj=newnext[j]endwhile(2.2)ifj=mthenmatch[i-(m-1)]=1j=next[m+1]i=i+1elsei=i+

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。