模式匹配的kmp算法

1、模式匹配的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

2、,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(t0,t1,t2,t3,tk-1)，于是原目标串可转化为T(p0,p1,p2,p3,pk-1，pk,tm-1)。在进行第二轮比较前，算法同样把字符串P整体向后移动一个字符，此时字符串T与P之间的关系如下： T p0,p1,p2,pk-1,pk, tn-2,tn-1,tm-2,tm-1 P p0,p1,p2,pk,pk+1,pn-2,pn-1(

3、第二轮比较)在第二轮比较中算法首先要比较的字符是P中首字符p0与T中第二个字符p1，若p0与p1相等，则算法顺序比较P中第二个字符p1与T中第三个字符p2；若不等，则算法仍然把模式串P整体向后移动一个字符，此时字符串T与P之间的关系如下 T p0,p1,p2,pk-1,pk, tn-2,tn-1,tm-2,tm-1P p0,pk-3,pk-2,pn-1（第三次比较）算法依照同样的次序，首先对P中字符p0与T中字符p2进行比较，若相等，则顺序比较后续的字母；若不等，则把字符串P整体向后移动一个字符。仔细考虑上述过程，可能会发现：在第二轮比较开始是，首先进行比较的字符是p0和p1，其次进行的是p1

4、和p2;在第三轮比较开始时，首先进行比较的是p0与p2，其次进行的是 p1和p3。而p0,p1,p2,p3全部是字符串P中的字符，它们之间的关系可以在调用字符串匹配算法前就确定下来。 KMP算法正式利用这种思想，算法在对字符串进行匹配前，先计算出，模式串P中个字符的关系，然后再依据此关系对模式串与目标串T进行匹配。在上述过程中，记录字符串P中各个字符之间关系的函数成为字符串P的失效函数。 下面是失效函数获取的办法（对于P=“caatcat”）： 首先确定函数的定义域，失效函数自变量j的取值范围是模式串在失配前匹配的字符个数，那么它的定义域为j0,1,2,3,4,5，由此可见失效函数的定义域是0

5、-len（p）-1。 接着是获取失效函数值域的办法，失效函数的取值k定义如下 Kk|0<=k<j其中，k是满足条件p0p1pk=pj-kpj-k+1pj的最大正整数。这样的k有可能并不存在，此时规定失效函数的取值为-1。下面是利用上述规则求字符串P的失效函数值域的过程： 当j=0时，由于0<=k<0,所以满足条件的k并不存在，此时失效函数的取值为-1，即f(0)=-1.当j=1时，k可能的取值为0，由于p0 p1，所以k不能取0，此时满足条件的失效函数的值仍为-1，即f(1)=-1。当j=2时，k的可能取值为0,1。由于p0p2且p0p1 p1p2，所以满足条件的k不存

6、在，即f(2)=-1。当j=3时，k可能的取值为0,1,2。由于p0p3，p0p1p2 p3且p0p1p2p1p2 p3。所以满足条件的k不存在，即f(3)=-1。当j=4时，k可能的取值为0,1,2,3。由于p0=p4，p0p1p3 p4，p0p1 p2p2 p3 p4且p0p1 p2 p3p1p2 p3 p4。所以满足条件的k为0，此时f(4)=0。当j=5时，k可能的取值为0,1,2,3,4。由于p0p5，p0p1= p4p5，p0p1p2p3 p4 p5，p0p1 p2 p3p2 p3 p4 p5且p0p1 p2 p3 p4p1p2 p3 p4 p5，所以f(5)=1;同理可求当j=6

7、时，f(6)=-1。求完模式串p的失效函数后，就可以应用KMP算法对它进行匹配。具体的匹配过程分为两种情况。假设在进行某一轮比较时，失配的情况发生在模式p的第j位，那么如果j=0，则让目标的指针前进一位，模式串的起始比较地址 回到P0处。否则，在进行下一轮的比较时，目标指针不发生回溯，仍指向失配的位置，而模式串的起始比较地址为Pf(j-1)+1.由失效函数的计算过程可见，函数f(j)仅与字符串P有关，而与目标串无关。所以只需给定模式字符串P，无论目标字符串T的取值是什么，均可应用同一个失配函数对它匹配。例子 模式串P=”caatcat”,目标串T=”ctcaatcacaatcat”。第一次比较

8、： T c t c a a t c a c a a t c a t P c a a t c a t第二轮比较： T c t c a a t c a c a a t c a t P c a a t c a t第三轮比较： T c t c a a t c a c a a t c a t P c a a t c a t第四轮比较： T c t c a a t c a c a a t c a t P c a a t c a t第一轮比较，模式串与目标串在第二个字符处发生匹配 。算法检测到失陪后结束本轮比较，并且指针不发生回溯，仍指向失配位置。由于失配发生在第二个字符处，此时j=1，所以模式匹配P在下一

9、轮匹配时的起始比较地址是P f(1-1)+1，即p0。第二轮比较中，由于模式字符串P所在的第一个字符处发生失配，此时j=0，所以让目标的指针前进一位，模式的其实比较位置回到p0。接着进行第三轮比较。模式串P中的第7个字符发生失配，此时j=6。可知下一轮匹配的起始比较位置为P f(6-1)+1，即p2。目标指针不发生回溯，仍指向失配位置。接着进行第四轮匹配，第四轮匹配成功。 T c t c a a t c a c a a t c a tP c a a t c a t （成功）#include<stdio.h>#include<string.h>char str1000,s

10、t1000;int next1000;void getf()int j=0,k=-1,m;next0=-1;m=strlen(st);while(j<m)if(k=-1|stj=stk)j+;k+;if(stj!=stk)nextj=k;else nextj=nextk;else k=nextk;for(j=0;j<m;j+)printf("%d ",nextj);int KMP()int i=0,j=0;memset(next,0,sizeof(next);getf();int m=strlen(str);int n=strlen(st);while(i<m&&