由此构造的函数∫同时满足前述性质1和2 2.串行随机串匹配算法 用上面定义的指纹函数可以构造一个随机串匹配算法。先计算模式串P(1,m)和子串 T(i,i+m1)的指纹函数(其中1≤i≤nm+1,m≤n),然后每当P的指纹和T(i,i+m-1) 的指纹相等时,则标记在文本T的位置i与P出现匹配。算法描述如下: 算法148串行随机串匹配算法 输入:数组T(1,n)和P(1,m),整数M。 输出:数组 MATCH,其分量指明P在T中出现的匹配位置 Begin (1)for i=l to n-m+l do end for (2)在区间[1,2,…,M中随机的选择一素数,并计算f2(P) (3)for i=l to n-m+l de Li= f,(r(i, i+m-D) end for (4)for i=l to n-m+l do if li=f,(p)then MATCH (i)=l end if end for End 很显然在该算法中步骤(1)和(4)的时间复杂度均为0(n-m);步骤(2)和(3)中 求模式串和文本串各个子串的指纹的时间复杂度分别O(m)和O(n-m) 122随机串匹配的并行算法 对上述串行算法的并行化主要是针对算法14.7中步骤(3)的并行处理,也就是说需要 选择一个合适的函数厂使其同时满足上述三个性质。前面一节给出了同时满足前两个性质 的函数,这里我们主要针对性质3来讨论已得指纹函数类F。 函数类F={Jn}的一个关键性质就是每个J都是同态( Homomorphic)的,即对于任 意两个串X和Y,fp(XY)=J(X)厂()。下面给出了一个有效的并行算法来计算文本串 7中所有子串的指纹。 对于每个1≤i≤mm+1,令N,=J(7(1,1),易得 N,=fp(7()J(7(2)…fp(()。因为矩阵乘法是可结合的,所以此计算就是一种前缀8 由此构造的函数 p f 同时满足前述性质 1 和 2。 2. 串行随机串匹配算法 用上面定义的指纹函数可以构造一个随机串匹配算法。先计算模式串 P（1，m）和子串 T（i，i+m-1）的指纹函数（其中 1≤i≤n-m+1，m≤n），然后每当 P 的指纹和 T（i，i+m-1） 的指纹相等时，则标记在文本 T 的位置 i 与 P 出现匹配。算法描述如下： 算法 14.8 串行随机串匹配算法 输入：数组 T(1，n)和 P(1，m)，整数 M。 输出：数组 MATCH，其分量指明 P 在 T 中出现的匹配位置。 Begin (1) for i=1 to n-m+1 do MATCH(i)=0 end for (2) 在区间[1，2，…，M]中随机的选择一素数，并计算 f (P) p (3) for i=1 to n-m+1 do Li= f (T(i,i + m −1)) p end for (4) for i=1 to n-m+1 do if Li= f (P) p then MATCH(i)=1 end if end for End 很显然在该算法中步骤（1）和（4）的时间复杂度均为 O（n-m）；步骤（2）和（3）中 求模式串和文本串各个子串的指纹的时间复杂度分别 O（m）和 O（n-m）。 1.2.2 随机串匹配的并行算法 对上述串行算法的并行化主要是针对算法 14.7 中步骤（3）的并行处理，也就是说需要 选择一个合适的函数 p f 使其同时满足上述三个性质。前面一节给出了同时满足前两个性质 的函数，这里我们主要针对性质 3 来讨论已得指纹函数类 F。 函数类 { }p F = f 的一个关键性质就是每个 p f 都是同态（Homomorphic）的，即对于任 意两个串 X 和 Y， f (XY) f (X ) f (Y) P = p p 。下面给出了一个有效的并行算法来计算文本串 T 中所有子串的指纹。 对于每个 1 ≤ i ≤ n-m+1 ， 令 N f (T(1,i)) i = p ，易得 N f (T(1)) f (T(2)) f (T(i)) i = p p  p 。因为矩阵乘法是可结合的，所以此计算就是一种前缀