附：求解next[j] 算法流程图:
i=1; j=0next[1]=0i next[2]=1 pnext[3]=1 pnext[4]=2 pnext[5]=2 pnext[6]=3 pnext[7]=1 pnext[8]=2 pnext[1]!= p1next[2]!= p= p2next[3]!= p3 next[4]4 next[5]= p5 next[6]!= p6 next[7]= p7 pnext[next[4]]= p4pnext[3]!=p6 pnext[3]!=p6next函数的改进算法 前面定义的next函数在某些情况下还是有缺陷例如：模式aaaab与主串aaabaaaab匹配情况： j：1 2 3 4 5模式：a a a a bnext[j]：0 1 2 3 4 i: 1 2 3 4 5 6 7 8 9S: a a a b a a a a b a a a a bT: a a a a ba a a a ba a a a ba a a a b 此时效率不高的原因为： 当Pj==Pnext[j]时，则 如果Si!= Pj，==》Si != Pnext[j] 因此，Si 没有必要继续与Pnext[j]进行比较，而应该直接和Pnext[j]的下一个字符Pnext[next[j]]进行比较。 因此，在计算next函数时，如果出现Pj=Pnext[j] =Pk 则next[j]=next[k]=next[next[j]]修改算法见教材P84 算法4.8 ④KMP算法的时间复杂度 回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为：(n-m+1)*m＝O(n*m) 而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法。 注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍 被采用。 KMP算法的用途：因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，?流式?作业！ 本章结束