end if end if end while End 在算法14.3中,内层 while循环遇到成功比较时和找到文本串中模式串的一个匹配位置 时文本串指针i均加1,所以至多做n次比较:;内 while循环每次不成功比较时文本串指针 保持不变,但是模式串指针j减小,所以i-j的值增加且上一次出内循环时的i一j值等于下 次进入时的值,因此不成功的比较次数不大于i-j的值的增加值,即小于n,所以总的比 较次数小于2n,所以算法143的时间复杂度为O(n)。算法144只比的算法142多计算了 next(m+1),至多多做m-1次比较,所以算法144的时间复杂度同样为O(m)。 112KMP串匹配的并行算法 1.算法原理 在介绍了改进的KMP串行算法基础上,这一节主要介绍如何在分布存储环境中对它进 行实现。设计的思路为:将长为n的文本串T均匀划分成互不重叠的p段,分布于处理器0 到p-1中,且使得相邻的文本段分布在相邻的处理器中,显然每个处理器中局部文本段的长 度为「n/p1(最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同)。再将长 为m的模式串P和模式串的 newnext函数播送到各处理器中。各处理器使用改进的KMP算 法并行地对局部文本段进行匹配,找到所有段内匹配位置。 但是每个局部段(第p-l段除外)段尾m-1字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器(处理器p1除外)将本局部段的段尾m-1个字符传送给下 处理器,下一处理器接收到前一处理器传来的字符串后,再接合本段的段首m-1个字符 构成一长为2(m-1)的段间字符串,对此字符串做匹配,就能找到所有段间匹配位置。但是算 法的通信量很大,采用下述两种改进通信的方法可以大大地降低通信复杂度:①降低播送模 式串和 newnext函数的通信复杂度。利用串的周期性质,先对模式串P作预处理,获得其最 小周期长度U、最小周期个数s及后缀长度Ⅳ(P=UV),只需播送U,s,Ⅳ和部分 newnext 函数就可以了,从而大大减少了播送模式串和 newnext函数的通信量。而且串的最小周期和 next函数之间的关系存在着下面定理1所示的简单规律,使得能够设计出常数时间复杂度的 串周期分析算法。②降低每个处理器(处理器p-1除外)将本局部文本段的段尾m-1个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长 前缀串,因为每个处理器上都有模式串信息,所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串P的最长前缀串降低到传送一个整数,从而大大地降低了通信 复杂度。而且KMP算法结束时模式串指针}1的值就是文本串尾模式串最大前缀串的长度, 这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度 串的周期性分析 定义141:给定串P,如果存在字符串U以及正整数K≥2,使得串P是串U的前缀 (Prefⅸx),则称字符串U为串P的周期( Period)。字符串P的所有周期中长度最短的周期 称为串P的最小周期( Maximal Period) 串的周期分析对最终并行算法设计非常关键,串的最小周期和next函数之间的关系存 在着如下定理141所示的简单规律,基于该规律可以设计出常数时间复杂度的串周期分析4 end if end if (3.5)j=j+1 end while End 在算法 14.3 中，内层 while 循环遇到成功比较时和找到文本串中模式串的一个匹配位置 时文本串指针 i 均加 1，所以至多做 n 次比较；内 while 循环每次不成功比较时文本串指针 i 保持不变，但是模式串指针 j 减小，所以 i－j 的值增加且上一次出内循环时的 i－j 值等于下 一次进入时的值，因此不成功的比较次数不大于 i－j 的值的增加值，即小于 n，所以总的比 较次数小于 2n，所以算法 14.3 的时间复杂度为 O（n）。算法 14.4 只比的算法 14.2 多计算了 next(m+1)，至多多做 m-1 次比较，所以算法 14.4 的时间复杂度同样为 O（m）。 1.1.2 KMP 串匹配的并行算法 1. 算法原理 在介绍了改进的 KMP 串行算法基础上，这一节主要介绍如何在分布存储环境中对它进 行实现。设计的思路为：将长为 n 的文本串 T 均匀划分成互不重叠的 p 段，分布于处理器 0 到 p-1 中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长 度为 n / p （最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同）。再将长 为 m 的模式串 P 和模式串的 newnext 函数播送到各处理器中。各处理器使用改进的 KMP 算 法并行地对局部文本段进行匹配，找到所有段内匹配位置。 但是每个局部段（第 p-1 段除外）段尾 m-1 字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器（处理器 p-1 除外）将本局部段的段尾 m-1 个字符传送给下 一处理器，下一处理器接收到前一处理器传来的字符串后，再接合本段的段首 m-1 个字符 构成一长为 2(m-1)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是算 法的通信量很大，采用下述两种改进通信的方法可以大大地降低通信复杂度：①降低播送模 式串和 newnext 函数的通信复杂度。利用串的周期性质，先对模式串 P 作预处理，获得其最 小周期长度|U|、最小周期个数 s 及后缀长度|V|（P=UsV），只需播送 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 所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析