作预处理，获得其最小周期长度|U|、最小周期个数s及后缀长度|V|（P=UV），只需播送U，s，|V|和部分newnext函数就可以了，从而大大减少了播送模式串和newnext函数的通信量。而且串的最小周期和next函数之间的关系存在着下面定理1所示的简单规律，使得能够设计出常数时间复杂度的串周期分析算法。②降低每个处理器（处理器p-1除外）将本局部文本段的段尾m-1个字符传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长前缀串，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这样就把通信量从传送模式串P的最长前缀串降低到传送一个整数，从而大大地降低了通信复杂度。而且KMP算法结束时模式串指针j-1的值就是文本串尾模式串最大前缀串的长度，这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度。
2. 串的周期性分析
定义14.1：给定串P，如果存在字符串U以及正整数K≥2，使得串P是串Uk的前缀（Prefix），则称字符串U为串P的周期（Period）。字符串P的所有周期中长度最短的周期称为串P的最小周期（Miximal Period）。
串的周期分析对最终并行算法设计非常关键，串的最小周期和next函数之间的关系存在着如下定理14.1所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析算法。
定理14.1：已知串P长为m，则u=m+1－next(m+1)为串P的最小周期长度。 算法 14.5 串周期分析算法 输入：next[m+1]
输出：最小周期长度period_len 最小周期个数period_num
模式串的后缀长度pattern-suffixlen procedure PERIOD_ANALYSIS Begin
period_len=m+1-next(m+1) period_num=(int)m/period_len pattern_suffixlen=m mod period_len End
3. 并行算法描述
在前述的串行算法以及对其并行实现计的分析的基础上，我们可以设计如下的并行KMP串匹配算法。 算法 14.6 并行KMP串匹配算法
输入：分布存储的文本串Ti[1，?n/p?]（i=0，1，2，…，p-1）
6
s
存储于P0的模式串P[1，m] 输出：所有的匹配位置 Begin
P0 call procedure NEXT /*调用算法14.4，求模式串P的 next函数和newnext函数*/
P0 call procedure PERIOD_ANALYSIS /*调用算法14.5分析P的周期*/
(2) P0 broadcast period_len，period_num，period_suffixlen to other processors
播送
P之最小周期长度、最小周期个数和后缀长度*/ P0 broadcast P[1，period_len]
/*不播送P之最小周期*/
if period_num=1 then /*播送P之部分newnext函数，如周期为1，则播送整个 newnext函数；否则播送2倍周期长的newnext函数*/ broadcast newnext [1，m] else
broadcast newnext[1，2*period_len] end if
(3) for i=1 to p-1 par-do /*由传送来的P之周期和部分newnext函数重构整个模式串 和newnext函数*/ Pi rebuild newnext end for
for i=1 to p-1 par-do /*调用算法14.7做局部段匹配，并获得局部段尾最大前缀串 之长度*/
Pi call procedure KMP(T，P ，n ，0，match) end for
(4) for i =0 to p-2 par-do Pi send maxprefixlen to Pi+1 end for
for i=1 to p-1 par-do
Pi receive maxprefixlen from Pi-1
Pi call procedure KMP(Ti，P，m-1， maxprefixlen，match+m-1) /*调用 算法14.7做段间匹配*/
/*
7
end for End
该算法中调用的KMP算法必须重新修改如下，因为做段间匹配时已经匹配了maxprefixlen长度的字符串，所以模式串指针只需从maxprefixlen+1处开始。
算法 14.7 重新修改的KMP算法
输入：分布存储的文本串和存储于P0的模式串P[1，m] 输出：所有的匹配位置
procedure KMP(T，P，textlen， matched_num，match) Begin (1) i=1
(2) j=matched_num+1 (3) while i≤textlen do
(3.1)while j≠0 and P[j]≠T[i] do j=newnext[j] end while (3.2)if j=m then match[i-(m-1)]=1 j=next[m+1] i=i+1 else j=j+1 i=i+1 end if end while
(4) maxprefixlen=j-1 End
下面从计算时间复杂度和通信时间复杂度两个方面来分析该算法的时间复杂度。在分析计算时间复杂度时，假定文本串初始已经分布在各个处理器上，这是合理的，因为文本串一般很大，不会有大的变化，只需要分布一次就可以，同时也假定结果分布在各处理器上。 本算法的计算时间由算法步（1）中所调用的算法14.4的时间复杂度O（m）和算法14.5的时间复杂度O（1）；算法步（3）和算法步（4）所调用的改进的KMP算法14.7的时间复杂度O（n/p）和O（m）构成。所以本算法总的计算时间复杂度为O（n/p+m）。
8
通信复杂度由算法步（2）播送模式串信息（最小周期串U及最小周期长度、周期个数和后缀长度三个整数）和newnext函数（长度为2u的整数数组，u为串U的长度）以及算法步（4）传送最大前缀串长度组成，所以通信复杂度与具体采用的播送算法有关。若采用二分树通信技术，则总的通信复杂度为O（ulogp）。
MPI源程序请参见章末附录。
2. 2、随机串匹配算法
2.1 随机串匹配及其串行算法
采用上一节所述的KMP算法虽然能够找到所有的匹配位置，但是算法的复杂度十分高，在某些领域并不实用。本节给出了随机串匹配算法，该算法的主要采用了散列（Hash）技术的思想，它能提供对数的时间复杂度。其基本思想是：为了处理模式长度为m的串匹配问题，可以将任意长为m的串映射到O(logm)整数位上，映射方法须得保证两个不同的串映射到同一整数的概率非常小。所得到的整数之被视为该串的指纹（Fingerprint），如果两个串的指纹相同则可以判断两个串相匹配。
1. 指纹函数
本节中假定文本串和模式串取字符集∑={0，1}中的字母。
如上所述，随机串匹配算法的基本策略是将串映射到某些小的整数上。令T是长度为n的文本串，P是长度为m≤n的模式串，匹配的目的就是识别P在T中出现的所有位置。考虑长度为m的T的所有子串集合B。这样的起始在位置i(1≤i≤n-m+1)的子串共有n-m+1个。于是问题可重新阐述为去识别与P相同的B中元素的问题。该算法中最重要的是如何选择一个合适的映射函数（Mapping Function），下面将对此进行简单的讨论。
令F?{fp}p?s是函数集，使得fp将长度为m的串映射到域D，且要求集合F满足下述三个性质：①对于任意串X∈B以及每一个p∈S（S为模式串的取值域），fp(X)由O（logm）位组成；②随机选择fp?F，它将两个不等的串X和Y映射到D中同一元素的概率是很小的；③对于每个p∈S和B中所有串，应该能够很容易的并行计算fp(X)。
上述三个性质中，性质①隐含着fp(X)和fp(P)可以在O(1)时间内比较，其中fp(X)被称为串X的指纹；性质②是说，如果两个串X和Y的指纹相等，则X=Y的概率很高；性质③主要是针对该算法的并行实现的需求对集合F加以限制。对于串行算法函数fp只需要满足前两个性质即可。
本节中我们采用了这样一类指纹函数：将取值{0，1}上的串X集合映射到取值整数环Z上的2?2矩
9
阵。令f(0)和f(1)定义如下：
?10?f(0)??，??11??11?f(1)????01?
该函数目前只满足性质2，为了使其同时满足性质1需要对该函数作如下更改：
令p是区间[1，2，…，M]中的一个素数，其中M是一个待指定的整数；令Zp是取模p的整数环。对于每个这样的p，我们定义fp(X)为f(X)modp，即fp(X)是一个2?2的矩阵，使得fp(X)的（i，j）项等于f(X)的相应项取模p。
由此构造的函数fp同时满足前述性质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]中随机的选择一素数，并计算fp(P) (3) for i=1 to n-m+1 do Li= fp(T(i,i?m?1)) end for
(4) for i=1 to n-m+1 do if Li=fp(P) then MATCH(i)=1 end if end for
10