模式匹配的kmp算法

1、模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt與1969年夏天提出的快速串匹配算法，它是由對BF算法的很大改進而成的，這主要體現(xiàn)在每當(dāng)某趟匹配失敗是，指針不必回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式向右“滑動“若干個位置后繼續(xù)比較。由于KMP算法避免了BF算法中頻繁的回溯，普遍提高了模式匹配的工作效率，因此它又被稱為“不回溯的字符串搜索算法”。假設(shè)有目標(biāo)串T(t0,t1,t2,t3,tm-1)和模式串P(p,p1,p2,p3,pn-1),使用BF算法進行模式匹配，當(dāng)進行第一輪比較時，若tkpk，則算法結(jié)束本輪比較，如下所示： 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 （第一輪比較結(jié)束）由于在字符串與中第一個不相等的字符位于處，所以兩字符串前個字符是相等的。此時，可用字符串P(p0,p1,p2,p3,pk-1) 字符串T(t0,t1,t2,t3,tk-1)，于是原目標(biāo)串可轉(zhuǎn)化為T(p0,p1,p2,p3,pk-1，pk,tm-1)。在進行第二輪比較前，算法同樣把字符串P整體向后移動一個字符，此時字符串T與P之間的關(guān)系如下： 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之間的關(guān)系如下 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進行比較，若相等，則順序比較后續(xù)的字母；若不等，則把字符串P整體向后移動一個字符。仔細(xì)考慮上述過程，可能會發(fā)現(xiàn)：在第二輪比較開始是，首先進行比較的字符是p0和p1，其次進行的是p1

4、和p2;在第三輪比較開始時，首先進行比較的是p0與p2，其次進行的是 p1和p3。而p0,p1,p2,p3全部是字符串P中的字符，它們之間的關(guān)系可以在調(diào)用字符串匹配算法前就確定下來。 KMP算法正式利用這種思想，算法在對字符串進行匹配前，先計算出，模式串P中個字符的關(guān)系，然后再依據(jù)此關(guān)系對模式串與目標(biāo)串T進行匹配。在上述過程中，記錄字符串P中各個字符之間關(guān)系的函數(shù)成為字符串P的失效函數(shù)。 下面是失效函數(shù)獲取的辦法（對于P=“caatcat”）： 首先確定函數(shù)的定義域，失效函數(shù)自變量j的取值范圍是模式串在失配前匹配的字符個數(shù)，那么它的定義域為j0,1,2,3,4,5，由此可見失效函數(shù)的定義域是0

5、-len（p）-1。 接著是獲取失效函數(shù)值域的辦法，失效函數(shù)的取值k定義如下 Kk|0<=k<j其中，k是滿足條件p0p1pk=pj-kpj-k+1pj的最大正整數(shù)。這樣的k有可能并不存在，此時規(guī)定失效函數(shù)的取值為-1。下面是利用上述規(guī)則求字符串P的失效函數(shù)值域的過程： 當(dāng)j=0時，由于0<=k<0,所以滿足條件的k并不存在，此時失效函數(shù)的取值為-1，即f(0)=-1.當(dāng)j=1時，k可能的取值為0，由于p0 p1，所以k不能取0，此時滿足條件的失效函數(shù)的值仍為-1，即f(1)=-1。當(dāng)j=2時，k的可能取值為0,1。由于p0p2且p0p1 p1p2，所以滿足條件的k不存

6、在，即f(2)=-1。當(dāng)j=3時，k可能的取值為0,1,2。由于p0p3，p0p1p2 p3且p0p1p2p1p2 p3。所以滿足條件的k不存在，即f(3)=-1。當(dāng)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。當(dāng)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;同理可求當(dāng)j=6

7、時，f(6)=-1。求完模式串p的失效函數(shù)后，就可以應(yīng)用KMP算法對它進行匹配。具體的匹配過程分為兩種情況。假設(shè)在進行某一輪比較時，失配的情況發(fā)生在模式p的第j位，那么如果j=0，則讓目標(biāo)的指針前進一位，模式串的起始比較地址 回到P0處。否則，在進行下一輪的比較時，目標(biāo)指針不發(fā)生回溯，仍指向失配的位置，而模式串的起始比較地址為Pf(j-1)+1.由失效函數(shù)的計算過程可見，函數(shù)f(j)僅與字符串P有關(guān)，而與目標(biāo)串無關(guān)。所以只需給定模式字符串P，無論目標(biāo)字符串T的取值是什么，均可應(yīng)用同一個失配函數(shù)對它匹配。例子 模式串P=”caatcat”,目標(biāo)串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第一輪比較，模式串與目標(biāo)串在第二個字符處發(fā)生匹配 。算法檢測到失陪后結(jié)束本輪比較，并且指針不發(fā)生回溯，仍指向失配位置。由于失配發(fā)生在第二個字符處，此時j=1，所以模式匹配P在下一

9、輪匹配時的起始比較地址是P f(1-1)+1，即p0。第二輪比較中，由于模式字符串P所在的第一個字符處發(fā)生失配，此時j=0，所以讓目標(biāo)的指針前進一位，模式的其實比較位置回到p0。接著進行第三輪比較。模式串P中的第7個字符發(fā)生失配，此時j=6?？芍乱惠喥ヅ涞钠鹗急容^位置為P f(6-1)+1，即p2。目標(biāo)指針不發(fā)生回溯，仍指向失配位置。接著進行第四輪匹配，第四輪匹配成功。 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&&