2串匹配 串匹配( String matching)问题是计算机科学中的一个基本问题,也是复杂性理论中研 究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学 等领域有着广泛的应用。而且,串匹配是这些应用中最耗时的核心问题,好的串匹配算法能 显著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值和实际意 串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子 串的起始位置。最基本的串匹配问题是关键词匹配( Keyword Matching)。所谓关键词匹配, 是指给定一个长为n的文本串1,n]和长为m的模式串P[1,m],找出文本串T中与模式 串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配( Perfect String matching)、 随机串匹配( Randomized String matching)和近似串匹配( Approximate String Matching)。 另外还有多维串匹配( Multidimensional String Matching和硬件串匹配( Hardware String Matching)等 本章中分别介绍改进的KMP串匹配算法,采用散列技术的随机串匹配算法,基于过滤 算法的近似串匹配算法,以及它们的MPI编程实现。 11KMP串匹配算法 111KMP串匹配及其串行算法 KMP算法首先是由 DE Knuth、JH.Mori以及ⅤR.Pa分别设计出来的,所以该算 法被命名为KMP算法。KMP串匹配算的基本思想是:对给出的的文本串T[1,n]与模式 串P[1,m],假设在模式匹配的进程中,执行币和P的匹配检查。若=P[,则继续 检查T计+和P[+1是否匹配。若≠P[,则分成两种情况:若j=1,则模式串右移一位 检查T计+1和P是否匹配;若1<j≤m,则模式串右移j- next()位,检查和P[next( 是否匹配(其中next是根据模式串P1,m]的本身局部匹配的信息构造而成的)。重复此过 程直到j=m或in结東 1.修改的KMP算法 在原算法基础上很多学者作了一些改进工作,其中之一就是重新定义了KMP算法中的 next函数,即求next函数时不但要求P[1,next(-1]=P-(next)-1),}1],而且要求 P[ next()≠P],记修改后的next函数为 newnext。在模式串字符重复高的情况下修改的 KMP算法比传统KMP算法更加有效。 算法141修改的KMP串匹配算法 输入:文本串71,n和模式串P[1,m] 输出:是否存在匹配位置 procedure modifed KMP Begi (1)i=1,j=1 (2) while i≤ndo (2) while j≠0andP[j]≠Tdo1 1. 2 串匹配 串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研 究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学 等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能 显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意 义。 串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子 串的起始位置。最基本的串匹配问题是关键词匹配（Keyword Matching）。所谓关键词匹配， 是指给定一个长为 n 的文本串 T[1，n]和长为 m 的模式串 P[1，m]，找出文本串 T 中与模式 串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配（Perfect String Matching）、 随机串匹配（Randomized String Matching）和近似串匹配（Approximate String Matching）。 另外还有多维串匹配（Multidimensional String Matching）和硬件串匹配（Hardware String Matching）等。 本章中分别介绍改进的 KMP 串匹配算法，采用散列技术的随机串匹配算法，基于过滤 算法的近似串匹配算法，以及它们的 MPI 编程实现。 1.1 KMP 串匹配算法 1.1.1 KMP 串匹配及其串行算法 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[j]，则分成两种情况：若 j=1，则模式串右移一位， 检查 T[i+1]和 P[1]是否匹配；若 1<j≤m，则模式串右移 j－next(j)位，检查 T[i]和 P[next(j)] 是否匹配（其中 next 是根据模式串 P[1，m]的本身局部匹配的信息构造而成的）。重复此过 程直到 j=m 或 i=n 结束。 1. 修改的 KMP 算法 在原算法基础上很多学者作了一些改进工作，其中之一就是重新定义了 KMP 算法中的 next 函数，即求 next 函数时不但要求 P[1，next(j) －1]=P[j－(next(j) －1)，j-1]，而且要求 P[next(j)] ≠P[j]，记修改后的 next 函数为 newnext。在模式串字符重复高的情况下修改的 KMP 算法比传统 KMP 算法更加有效。 算法 14.1 修改的 KMP 串匹配算法 输入：文本串 T[1，n]和模式串 P[1，m] 输出：是否存在匹配位置 procedure modeifed_KMP Begin (1) i=1,j=1 (2) while i≤n do (2.1)while j≠0 and P[j]≠T[i] do