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

《并行计算实验指导(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+