文档介绍：模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt与1969年夏天提出的快速串匹配算法,它是由对BF算法的很大改进而成的,这主要体现在每当某趟匹配失败是,指针不必回溯,而是利用已经得到的“部分匹配”结果,将模式向右“滑动“若干个位置后继续比较。由于KMP算法避免了BF算法中频繁的回溯,普遍提高了模式匹配的工作效率,因此它又被称为“不回溯的字符串搜索算法”。假设有目标串T(t0,t1,t2,t3……,tm-1)和模式串P(p0,p1,p2,p3,…pn-1),使用BF算法进行模式匹配,当进行第一轮比较时,若tk≠pk,则算法结束本轮比较,如下所示:Tt0,t1,t2,…tk,tk+1,…tn-2,tn-1,…tm-2,tm-1Pp0,p1,p2,…pk,pk+1…,pn-2,pn-1(第一轮比较结束)由于在字符串T与P中第一个不相等的字符位于k处,所以两字符串前k个字符是相等的。此时,可用字符串P(p0,p1,p2,p3,…pk-1)字符串T(t0,t1,t2,t3……,tk-1),于是原目标串可转化为T(p0,p1,p2,p3,…pk-1,pk……,tm-1)。在进行第二轮比较前,算法同样把字符串P整体向后移动一个字符,此时字符串T与P之间的关系如下:Tp0,p1,p2,…pk-1,pk,…tn-2,tn-1,…tm-2,tm-1Pp0,p1,p2,…pk,pk+1…,pn-2,pn-1(第二轮比较)在第二轮比较中算法首先要比较的字符是P中首字符p0与T中第二个字符p1,若p0与p1相等,则算法顺序比较P中第二个字符p1与T中第三个字符p2;若不等,则算法仍然把模式串P整体向后移动一个字符,此时字符串T与P之间的关系如下Tp0,p1,p2,…pk-1,pk,…tn-2,tn-1,…tm-2,tm-1Pp0,…pk-3,pk-2,…,pn-1(第三次比较)算法依照同样的次序,首先对P中字符p0与T中字符p2进行比较,若相等,则顺序比较后续的字母;若不等,则把字符串P整体向后移动一个字符。仔细考虑上述过程,可能会发现:在第二轮比较开始是,首先进行比较的字符是p0和p1,其次进行的是p1和p2;在第三轮比较开始时,首先进行比较的是p0与p2,其次进行的是p1和p3。而p0,p1,p2,p3全部是字符串P中的字符,它们之间的关系可以在调用字符串匹配算法前就确定下来。KMP算法正式利用这种思想,算法在对字符串进行匹配前,先计算出,模式串P中个字符的关系,然后再依据此关系对模式串与目标串T进行匹配。在上述过程中,记录字符串P中各个字符之间关系的函数成为字符串P的失效函数。下面是失效函数获取的办法(对于P=“caatcat”):首先确定函数的定义域,失效函数自变量j的取值范围是模式串在失配前匹配的字符个数,那么它的定义域为j{0,1,2,3,4,5},由此可见失效函数的定义域是0-len(p)-1。接着是获取失效函数值域的办法,失效函数的取值k定义如下K{k|0<=k<j}其中,k是满足条件p0p1…pk=pj-kpj-k+1…pj的最大正整数。这样的k有可能并不存在,此时规定失效函数的取值为-1。下面是利用上述规则求字符串P的失效函数值域的过程:当j=0时,由于0<=k<0,所以满足条件的k并不存在,此时失效函数的取值为-1,即f(0)=-1