算法。 定理141:已知串P长为m,则u=m+1-next(m+1)为串P的最小周期长度。 算法145串周期分析算法 输入:next[m+ 输出:最小周期长度 period len 最小周期个数 period num 模式串的后缀长度 pattern- suffixlen procedure PERIOD ANALYSIS B period len=m+1-next(m+1) period num=(int )m/pe pattern suffixlen=m mod period ler 3.并行算法描述 在前述的串行算法以及对其并行实现计的分析的基础上,我们可以设计如下的并行 KMP串匹配算法。 算法146并行KMP串匹配算法 输入:分布存储的文本串T1,m/p(i=0,1,2, 存储于PO的模式串P[1,ml 输出:所有的匹配位置 Be (1) Po call procedure NEXT/*调用算法144,求模式串P的 next函数和 newnext函数* Po call procedure PERIOD ANALYSIS陣*调用算法14.5分析P的周期*/ (2) Po broadcast period len, period num, period suffixlen to other processors /*fhit P之最小周期长度、最小周期个数和后缀长度* Po broadcast P[, period len]/*不播送P之最小周期* if period num= I then/播送P之部分 newnext函数,如周期为1,则播送整个 newnext函数:否则播送2倍周期长的 newnext函数* broadcast newnext [1, m broadcast newnext[ 1, 2*period len end if (3)fori= I to p-l par-do/*由传送来的P之周期和部分 newnext函数重构整个模式串 和 newnext函数* Pi rebuild newnext end for fori=ltop- I par-do/调用算法147做局部段匹配,并获得局部段尾最大前缀串 之长度* Pi call procedure KMP(T, P, n, 0, match) end for (4)for i=0 to p-2 par-de5 算法。 定理 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） 存储于 P0 的模式串 P[1，m] 输出：所有的匹配位置 Begin (1) 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