2串匹配.docVIP

2 串匹配 串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（eyword 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编程实现。 KMP串匹配算法 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]是否匹配；若1j≤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][next(j)] ≠P[j]，记修改后的next函数为newnext。在模式串字符重复高的情况下修改的KMP算法比传统KMP算法更加有效。 算法 14.1 修改的KMP串匹配算法 输入：文本串T[1，n][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 j=newnext[j] end while (2.2)if j=m then return true else j=j+1,i=i+1 end if end while (3) return false End 算法 14.2 next函数和newnext函数的计算算法 输入：模式串P[1，m] next[1，m+1]newnext[1，m]procedure next Begin (1) next[1]=0 (2) j=2 (3) while j≤m do (3.1)i=next[j-1] (3.2)while i≠0 and P[i]≠P[j-1] do i=next[i] end while (3.3)next[j]=i+1 (3.4)j=j+1 end while End procedure newnext Begin (1) newnext(1)=0 (2) j=2 (3) while j≤m do (3.1)i=next(j) (3.2)if i=0 or P[j]≠P[i+1] then newnext[j]=i else newnext[j]=newnext[i] end if (3.3)j=j+1 end while End 2. 改进的KMP算法 易知算法14.1的时间复杂度为O（n），算法14.2的时间复杂度为O（m）。算法14.1中所给出的KMP算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。下面给出改进后的算法14.3便解决了这一问题。 算法 14.3 改进KMP串匹配算法 输入：文本串T[1，n]和模式串P[1，m] match[1，n]procedure improved_KMP Begin (1) i=1，j=1 (2) while i≤n do (2.1)while j≠0 and P[j]≠T[i] do j=newnext[j] end while (2.2)if j