2.改进的KMP算法 易知算法141的时间复杂度为O(n),算法142的时间复杂度为O(m)。算法14.1 中所给出的KMP算法只能找到第一个匹配位置,实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法14.3便解决了这一问题。 算法143改进KMP串匹配算法 输入:文本串丌1,n和模式串P[,m] 输出:匹配结果 match1,n procedure improved KMP Begin (2) while i≤ndo (21) while j≠0andP[≠T[do end while (2.2)if j=m then match i-(m-D)=I j= next[m+l =1+1 j+1 end if end while max prefix I 算法144next函数和 newnext函数的计算算法 输入:模式串P[1,m] 输出;next1,m+1和 newnext[1,m procedure NEXT (1)next[1]=newnext[ 11=0 (3) while j≤m+1do (3.2) while i≠0andW[≠W-1])do end while (3.3)next=i+l (34)ifj≠m+ I then ifW≠w[i+ 1] then newnext[]=i+I newnext[=newnext[i+ll3 2. 改进的 KMP 算法 易知算法 14.1 的时间复杂度为 O（n），算法 14.2 的时间复杂度为 O（m）。算法 14.1 中所给出的 KMP 算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法 14.3 便解决了这一问题。 算法 14.3 改进 KMP 串匹配算法 输入：文本串 T[1，n]和模式串 P[1，m] 输出：匹配结果 match[1，n] procedure improved_KMP Begin (1) i=1，j=1 (2) while i≤n do (2.1)while j≠0 and P[j]≠T[i] do j=newnext[j] end while (2.2)if j=m then match[i-(m-1)]=1 j=next[m+1] i=i+1 else i=i+1 j=j+1 end if end while (3) max_prefix_len=j-1 End 算法 14.4 next 函数和 newnext 函数的计算算法 输入：模式串 P[1，m] 输出：next[1，m+1]和 newnext[1，m] procedure NEXT Begin (1) next[1]=newnext[1]=0 (2) j=2 (3) while j≤m+1 do (3.1)i=next[j-1] (3.2)while i≠0 and W[i]≠W[j-1]) do i=next[i] end while (3.3)next[j]=i+1 (3.4)if j≠m+1 then if W[j] ≠W[i+1] then newnext[j]=i+1 else newnext[j]=newnext[i+1]