32 改进的摸式区配算法—KMP算法 i=1i=2i3 D.E.Knuth与 第1趟S VR.Pratt和 a b.baba T a b J.H.Morris同时发现 a 的，故简称为MP算 法 第2趟S a bb a b a 指针不回湖！ T a =4i=5i6i= 第3趟S a bb ab T a b a 返回=4
33 改进的摸式西配算法—KMP(2) 第1趟S a b a b c a b c acba b T a b.c a c 每当出现失配时，指针不回 溯，而是利用已经得到的“部分 4 匹配”结果将模式向右“滑动”尽 可能远的一段距离后，继续比较 第2趟S a b ab c al b c a cb a b T j12j34 7i=8i9i=1010 第3趟S·a b a b c a b c,acba b T (a)b c a c 返回i=6 ◆◆ 臣23j456