《数据结构》课程教学资源：第四章 串 4.3串的模式匹配算法 44串操作应用举例

改进的模式匹配算法——KMP算法 i=1i=2i=3 D.E. Knuth与 第1趟S·ab.baba V.R. Pratt/fu Ta b a J.H. Morris同时发现。 的,故简称为KMP算 法 第2趟 s ab b a b a 不回湖! T b a i=4i=5i=6i=7 第3趟 s abb ba T b a 返回i=4

改进的模式匹配算法——KMP(2) i=1i=2i=3 第1趟 s. ab bca bcacba b T a b c a c 每当出现失配时,i指针和回 溯,而是利用已经得到的“部分 21213匹配”结果将模式向右“滑动”尽 可能远的一段距离后,继续比较 第2趟Saba, b c abc, a cb a b j=1j=2 j13j=4j =7i=8i=9i=10i=11 第3趟 s a b ab cabc, a cb ab ab 返回=6 2j=3j=4j=5j=6