数据结构课件- 河南大学精品课程网 - 图文 -(6)

附：求解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不必回溯，所以从外存输入文件时可以做到边读入边查找，?流式?作业！

本章结束

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课件- 河南大学精品课程网 - 图文 -(6)在线全文阅读。