Pi send maxprefixlen to Pi for iI to p-l par-do Pi receive maxprefixlen from Pi-1 call procedure KMP(Ti, P, m-1, maxprefixlen, match+m-1)/*iHH 算法147做段间匹配* end for End 该算法中调用的KMP算法必须重新修改如下,因为做段间匹配时已经匹配了 axprefixlen长度的字符串,所以模式串指针只需从 maxprefixlen+1处开始 算法14.7重新修改的KMP算法 输入:分布存储的文本串和存储于P的模式串P[1,m 输出:所有的匹配位置 procedure KMP(T, P, textlen, matched num, match) Begin l (2)j=matched num+ (3) while i≤ textlen d (3.1) while j≠0andP]≠Tdo end while (3.2)ifj=m the match i-(m-D=I next[m+1 =1+1 else I=1+1 end if end while (4)maxprefixlen=j-1 下面从计算时间复杂度和通信时间复杂度两个方面来分析该算法的时间复杂度。在分析 计算时间复杂度时,假定文本串初始已经分布在各个处理器上,这是合理的,因为文本串 般很大,不会有大的变化,只需要分布一次就可以,同时也假定结果分布在各处理器上。本 算法的计算时间由算法步(1)中所调用的算法144的时间复杂度O(m)和算法145的时 间复杂度O(1);算法步(3)和算法步(4)所调用的改进的KMP算法14.7的时间复杂度 O(np)和O(m)构成。所以本算法总的计算时间复杂度为O(n/p+m)。通信复杂度由算 法步(2)播送模式串信息(最小周期串U及最小周期长度、周期个数和后缀长度三个整数) 和 newnext函数(长度为2u的整数数组,u为串U的长度)以及算法步(4)传送最大前缀 串长度组成,所以通信复杂度与具体采用的播送算法有关。若采用二分树通信技术,则总的 通信复杂度为O(uogp) MPI源程序请参见章末附录。 66 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 做段间匹配*/ 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）。通信复杂度由算 法步（2）播送模式串信息（最小周期串 U 及最小周期长度、周期个数和后缀长度三个整数） 和 newnext 函数（长度为 2u 的整数数组，u 为串 U 的长度）以及算法步（4）传送最大前缀 串长度组成，所以通信复杂度与具体采用的播送算法有关。若采用二分树通信技术，则总的 通信复杂度为 O（ulogp）。 MPI 源程序请参见章末附录