a a N=0 KMP算法的效率 s=tabla 两重循环 I=2=1,NU1]=0 afor循环最多执行n= S strlen(次 I=7」=4N1]=3 其内部的 while循环,最长循环 aa a 复a 次数是m= P strlen次 =8=4N1]=3 初看起来其时间开销也可能达 b aa a ac√ 到O(n×m) 大卿血端_权,究 京太盒帖写c有, a循环体中“j=N-1”语句的执行次 数不能超过加次。否则, 由手宁NH;”每执行一次必然使 另一种next数组方法 得j减少(至少减1) ■序号012345678 ■而使得j增加的操作只有“j++” a b c aa b a bc 那么,如果“jNi1;”的执行次数 k 00011212 超过n次,最终的结果必然使得为 负数。这是不可能的 p=p1?≠≠=≠=≠== m同理可以分析出求next数组的时间 nex-100-110200 为o(m) 因此,KMP算法的时间为o(n+m) nexy 大带_息 张写 积新有,神 张所有,赖 序号i012345678 序号i012345678 b a b HM匹配 P一P HM匹配 000112123 目标 aabcbabcaabcaababc 第1趟目标 aabcbabcaabcaababc caababc next(1=o 莫式 a kc aa b a bcagbabc nex4(3)=-1 第2趟目标 aabcbabcaabcaababc bcaa babc x next(6=2 abcnababc next(2=0 abcaababc 第3趟目标 aabelabcaabcaababe &beaab abc j 第4趙目标 aabcbabcaabcaababc abca 第5趙目标 aabcbabcaabcaababc 模式 (a bcaababe 北底大 张储帖写 中w8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 back next P = a a a b a a a 0 12 3 4 5 6 N = 0 1 2 3 0 1 2 3 4 0 a a c 789 S = a b a a a a a 0 12 3 4 5 6 a a b 789 a a a a c b 10 11 12 13 14 P = a a Xa a b a a a a c i=2, j=1, N[j-1]=0 i=2, j=2, N[j-1]=1 a a a a Xb a a a a c i=7, j=4, N[j-1]=3 a a a a Xb a a a a c i=8, j=4, N[j-1]=3 a a a a b a a a a c √ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 back next KMP算法的效率 „ 两重循环 „ for循环最多执行n＝S.strlen()次 „ 其内部的while循环，最长循环 次数是m＝P.strlen()次。 „ 初看起来其时间开销也可能达 到O(n×m)。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 back next „ 循环体中“j=N[j-1];”语句的执行次 数不能超过n次。否则， „ 由于“j= N[j-1];”每执行一次必然使 得j减少(至少减1) „ 而使得j增加的操作只有“j++” „ 那么，如果“j= N[j-1];”的执行次数 超过n次，最终的结果必然使得j为 负数。这是不可能的。 „ 同理可以分析出求next数组的时间 为O(m) „ 因此，KMP算法的时间为Ｏ(n+m) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 back next 另一种next数组方法 „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 pk==pi ? ≠ ≠ == ≠ == ≠ == == next[i] -1 0 0 -1 1 0 2 0 0 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 back next KMP匹配 目标 a a b c b a b c a a b c a a b a b c a b c a a b a b c a b c a a b a b c a b c a a b a b c a b c a a b a b c √ × „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 pk==pi ? ≠ ≠ == ≠ == ≠ == == next[i] -1 0 0 -1 1 0 2 0 0 next(1) = 0 × next(3) = -1 × next(6) = 2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 back next KMP匹配 第1趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(0) = 0 第2趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(2)= 0 第3趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c j==0 第4趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(5) = 2 第5趟 目标 a a b c b a b c a a b c a a b a b c 模式 (a b) c a a b a b c √ × × × „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 3 ×