End
很显然在该算法中步骤（1）和（4）的时间复杂度均为O（n-m）；步骤（2）和（3）中求模式串和文本串各个子串的指纹的时间复杂度分别O（m）和O（n-m）。
2.2 随机串匹配的并行算法
对上述串行算法的并行化主要是针对算法14.7中步骤（3）的并行处理，也就是说需要选择一个合适的函数fp使其同时满足上述三个性质。前面一节给出了同时满足前两个性质的函数，这里我们主要针对性质3来讨论已得指纹函数类F。
函数类F?{fp}的一个关键性质就是每个fp都是同态（Homomorphic）的，即对于任意两个串X和Y，
fP(XY)?fp(X)fp(Y)。下面给出了一个有效的并行算法来计算文本串T中所有子串的指纹。
对于每个1≤i≤n-m+1，令Ni?fp(T(1,i))，易得Ni?fp(T(1))fp(T(2))?fp(T(i))。因为矩阵乘法是可结合的，所以此计算就是一种前缀和的计算；同时每个矩阵的大小为2?2，因此这样的矩阵乘法可以在O（1）时间内完成。所以，所有的Ni都可以在O（logn）时间内，总共使用O（n）次操作计算。
定义
14.2：
0??1?1?1gp(0)?fp(0)?1??,g(1)?f(1)?p?p?0?p?11??p?1?。则乘积1??Ri?gp(T(i))gp(T(i?1))?gp(T(1))也是一个前缀和计算，并且对于1?i?n，它可以在O（logn）时
间内运用O（n）次操作计算。
容易看到，fp(T(i,i?m?1))?Ri?1Ni?m?1，因此，一旦所有的Ri和Ni都计算出来了，则每个这样的矩阵均可在O（1）时间内计算之。所以，长度为n的正文串T中所有长度为m≤n的子串的指纹均可在O（logn）时间内使用O（n）次操作而计算之。
这样，函数fp同时满足了前述三个性质。在此基础上我们给出了在分布式存储体系结构上随机串匹配的并行算法。
算法 14.9 并行随机串匹配算法 输入：数组T(1，n)和P(1，m)，整数M。
输出：数组MATCH，其分量指明P在T中出现的位置。 Begin
(1) for i=1 to n-m+1 par-do MATCH(i)=0;
11
end for
(2) Select a random prime number in [1，2，…，M]，then count fp(P)。 (3) for i=1 to n-m+1 par-do Li= fp(T(i,i?m?1)); end for
(4) for i=1 to n-m+1 par-do if Li=fp(P) then MATCH(i)=1 end if end for End
该并行算法的计算复杂度为O（logn）。处理期间的通信包括在对文本串到各个处理器的分派，其通信复杂度为O（n/p+m）；以及匹配信息的收集，其通信复杂度为O（n/p）。
MPI源程序请参见所附光盘。
3. 3、近似串匹配算法
3.1 近似串匹配及其串行算法
前两节所讨论的串匹配算法均属于精确串匹配技术，它要求模式串与文本串的子串完全匹配，不允许有错误。然而在许多实际情况中，并不要求模式串与文本串的子串完全精确地匹配，因为模式串和文本串都有可能并不是完全准确的。例如，在检索文本时，文本中可能存在一些拼写错误，而待检索的关键字也可能存在输入或拼写错误。在这种情况下的串匹配问题就是近似串匹配问题。
近似串匹配问题主要是指按照一定的近似标准，在文本串中找出所有与模式串近似匹配的子串。近似串匹配问题的算法有很多，按照研究方法的不同大致分为动态规划算法，有限自动机算法，过滤算法等。但上述所有算法都是针对一般的近似串匹配问题，也就是只允许有插入、删除、替换这三种操作的情况。本节中还考虑了另外一种很常见的错误—换位，即，文本串或模式串中相邻两字符的位置发生了交换，这是在手写和用键盘进行输入时经常会发生的一类错误。为修正这类错误引入了换位操作，讨论了允许有插入、删除、替换和换位四种操作的近似串匹配问题。
1. 问题描述:
12
给定两个长度分别为m和n的字符串A[1，m]和B[1，n]，ai，bj∈∑(1≤i≤m，1≤j≤n，∑是字母表)，串A与串B的编辑距离（Editor Distance）是指将串A变成串B所需要的最少编辑操作的个数。最常见的编辑操作有三种：①插入(Insert)，向串A中插入一个字符；②删除(Delete)，从串A中删除一个字符；③替换(Replace)，将串A中的一个字符替换成串B中的一个字符。其中，每个编辑操作修正的串A与串B之间的一个不同之处称为一个误差或者错误。
最多带k个误差的串匹配问题（简称为k-differences问题）可描述如下：给定一个长度为n的文本串T=t1…tn，一个长度为m的模式串P=p1…pm，以及整数k（k≥1），在文本串T中进行匹配查找，如果T的某个子串ti…tj与模式串P的编辑距离小于等于k，则称在tj处匹配成功，要求找出所有这样的匹配结束位置tj。
另外一种很常见的编辑操作是换位(Exchange)：将串A中的两个相邻字符进行交换。该操作用于修正相邻两字符位置互换的错误。一个换位操作相当于一个插入操作加上一个删除操作。但是，当近似匹配允许的最大误差数k一定时，允许有换位操作的情况较之不允许有换位操作的情况，往往能够找出更多的匹配位置。
例如，假定文本串T=abcdefghij，模式串P=bxcegfhy，k=4，问在文本串的第9个字符处是否存在最多带4个误差的匹配？
首先考虑允许有换位操作的情况，文本串与模式串的对应关系如下： t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 T:
a b c d e f g h i j
P: b x c e g f h y
① ② ③ ④
其中，①，②，③，④ 4个位置分别对应于删除、插入、换位和替换操作，可见在t9处确实有最多带4个误差的匹配。
不允许有换位操作的情况，对应关系如下： t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 T: a b c d e f g h i j P: b x c e g f h y ① ② ③ ④ ⑤
可以看出，在t9处不存在最多带4个误差的匹配，因为匹配成功所需要的最少编辑操作个数为5。 由此可见，允许有换位操作的近似串匹配算法比以往未考虑换位操作的算法更加实用有效。尤其是在文本检索和手写体识别等实际应用中，新算法的检索成功率和识别率更高，准确性更好，功能更强。
2. k-differences问题的动态规划算法
13
一般的k-differences问题的一个著名算法采用了动态规划（Dynamic Programming）的技术，可以在O（mn）时间内解决该问题。其基本思想是：根据文本串T[1，n]和模式串P[1，m]计算矩阵D(m+1)x(n+1)，其中D[i，j](0≤i≤m，0≤j≤n)是模式串P的前缀子串p1…pi与文本串T的任意以tj结尾的子串之间的最小误差个数（即最小编辑距离）。显然，如果D[m，j] ≤k，则表明在文本串T的tj处存在最多带k个误差的匹配。D[i，j]由以下公式计算：
D[0，j]=0，0≤j≤n D[i，0]=i，1≤i≤m
D[i，j]=min(D[i-1，j]+1，D[i，j-1]+1，D[i-1，j-1]+δ(pi，tj)) 其中，δ(pi，tj)=0，如果pi=tj；否则，δ(pi，tj)=1。
可以看出，D[i，j]的计算是通过递推方式进行的。D[0，j]对应于模式串为空串，而文本串长度为j的情况，显然，空串不需要任何编辑操作就能在文本串的任何位置处匹配，所以D[0，j]=0。D[i，0]对应于模式串长度为i，而文本串为空串的情况，此时，至少需要对模式串进行i次删除操作才能与文本串（空串）匹配，所以D[i，0]=i。在计算D[i，j]时，D[i-1，j]，D[i，j-1]，D[i-1，j-1]都已计算出，D[i-1，j]+1，D[i，j-1]+1，D[i-1，j-1]+δ(pi，tj)分别对应于对模式串进行插入、删除、替换操作的情况，由于D[i，j]是最小编辑距离，所以取三者中的最小值。
上述动态规划算法只考虑了插入、删除、替换三种编辑操作，但很容易将其推广到允许有换位操作的情况。考虑D[i，j]的计算，若pi-1pi=titi-1，则D[i，j]的一个可能取值是D[i-2，j-2]+1，即，将pi-1pi变成titi-1只需要进行一次换位操作，从而最小编辑距离只增加1。由此可对上述算法进行简单的修改，使之适用于允许有插入、删除、替换和换位四种编辑操作的情况。
算法14.10 允许有换位操作的k-differences问题的动态规划算法。 输入：文本串T[1，n]，模式串P[1，m]，近似匹配允许的最大误差数k。 输出：所有匹配位置。
K-Diff_DynamicProgramming(T，n，P，m，k) Begin
(1) for j=0 to n do D[0,j]=0 end for (2) (3)
for i=1 to m do D[i,0]=i end for for i=1 to m do
(3.1) for j=1 to n do
(ⅰ)
if (P[i]=T[j]) then D[i,j]=D[i-1,j-1]
else if (P[i]=T[j-1] and P[i-1]=T[j]) then
14
D[i,j]=min(D[i-2,j-2]+1,D[i-1,j]+1,D[i,j-1]+1)
else
D[i,j]=min(D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+1)
end if end if
(ⅱ) if (i=m and D[i,j]<=k) then
找到P在T中的一个最多带k个误差的近似匹配， 输出匹配结束位置j； end if end for end for
End
显然，该算法的时间复杂度为O（mn）。 3. 基于过滤思想的扩展的近似串匹配算法:
经典的动态规划算法在实际应用中速度很慢，往往不能满足实际问题的需要。为此，S.Wu和U.Manber以及Gonzalo Navarro和Ricardo Baeza-Yates等人先后提出了多个基于过滤(Filtration)思想的更加快速的近似串匹配算法。这些算法一般分为两步：①按照一定的过滤原则搜索文本串，过滤掉那些不可能发生匹配的文本段；②再进一步验证剩下的匹配候选位置处是否真的存在成功匹配。由于在第一步中已经滤去了大部分不可能发生匹配的文本段，因此大大加速了匹配查找过程。在实际应用中，这些过滤算法一般速度都很快。下面我们针对前面定义的扩展的近似串匹配问题，讨论了加入换位操作后的k-differences问题的过滤算法。
过滤算法基于这样一种直观的认识：若模式串P在文本串T的tj处有一个最多带k个误差的近似匹配，则P中必然有一些子串是不带误差地出现在T中的，也就是说，P中必然有一些子串与T中的某些子串是精确匹配的。
引理14.1：在允许有换位操作的最多带k个误差的串匹配问题中，如果将模式串P划分成2k+1段，那么对于P在T中的每一次近似出现（最多带k个误差），这2k+1段中至少有一段是不带误差地出现在T中的。
证明：这个引理很容易证明。试想，将k个误差，也就是对模式串P所做的k个编辑操作，分布于2k+1个子模式串中。由于一个插入，删除或替换操作只能改变一个子模式串，而一个换位操作有可能改变两个子模式串（例如，在子模式串i的最后一个字符与子模式串i+1的第一个字符之间进行一次换位操作），所以k个编辑操作最多只能改变2k个子模式串。这就是说，在这2k+1个子模式串中，至少有一个是未被
15