KMP算法(改进版)5页.doc

4.3.2 模式匹配的一种改进算法这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。下面先从具体例子看起。 i=3第一趟匹配 a b a b c a b c a c b a b a b c j=3 i3第二趟匹配 a b a b c a b c a c b a b a b c a c j=5 j=1 i i=11第三趟匹配 a b a b c a b c a c b a b