精选优质文档-倾情为你奉上模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt与1969年夏天提出的快速串匹配算法，它是由对BF算法的很大改进而成的，这主要体现在每当某趟匹配失败是，指针不必回溯，而是利用已经得到的“部分匹配”结果，将模式向右“滑动“若干个位置后继续比较。由于KMP算法避免了BF算法中频繁的回溯，普遍提高了模式匹配的工作效率，因此它又被称为“不回溯的字符串搜索算法”。假设有目标串T(t0,t1,t2,t3,tm-1)和模式串P(p,p1,p2,p3,pn-1),使用BF算法进行模式匹配，当进行第一轮比较时，若tkpk，则算法结束本轮比较，如下所示： T t0,t1,t2,tk,tk+1,tn-2,tn-1,tm-2,tm-1 P p0,p1,p2,pk,pk+1,pn-2,pn-1 （第一轮比较结束）由于在字符串与中第一个不相等的字符位于处，所以两字符串前个字符是相等的。此时，可用字符串P(p0,p1,p2,p3,pk-1) 字符串T
