模式匹配的kmp算法

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

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

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

6、在，即f(2)=-1。當(dāng)j=3時(shí)，k可能的取值為0,1,2。由于p0p3，p0p1p2 p3且p0p1p2p1p2 p3。所以滿(mǎn)足條件的k不存在，即f(3)=-1。當(dāng)j=4時(shí)，k可能的取值為0,1,2,3。由于p0=p4，p0p1p3 p4，p0p1 p2p2 p3 p4且p0p1 p2 p3p1p2 p3 p4。所以滿(mǎn)足條件的k為0，此時(shí)f(4)=0。當(dāng)j=5時(shí)，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、時(shí)，f(6)=-1。求完模式串p的失效函數(shù)后，就可以應(yīng)用KMP算法對(duì)它進(jìn)行匹配。具體的匹配過(guò)程分為兩種情況。假設(shè)在進(jìn)行某一輪比較時(shí)，失配的情況發(fā)生在模式p的第j位，那么如果j=0，則讓目標(biāo)的指針前進(jìn)一位，模式串的起始比較地址 回到P0處。否則，在進(jìn)行下一輪的比較時(shí)，目標(biāo)指針不發(fā)生回溯，仍指向失配的位置，而模式串的起始比較地址為Pf(j-1)+1.由失效函數(shù)的計(jì)算過(guò)程可見(jiàn)，函數(shù)f(j)僅與字符串P有關(guān)，而與目標(biāo)串無(wú)關(guān)。所以只需給定模式字符串P，無(wú)論目標(biāo)字符串T的取值是什么，均可應(yīng)用同一個(gè)失配函數(shù)對(duì)它匹配。例子 模式串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)串在第二個(gè)字符處發(fā)生匹配 。算法檢測(cè)到失陪后結(jié)束本輪比較，并且指針不發(fā)生回溯，仍指向失配位置。由于失配發(fā)生在第二個(gè)字符處，此時(shí)j=1，所以模式匹配P在下一

9、輪匹配時(shí)的起始比較地址是P f(1-1)+1，即p0。第二輪比較中，由于模式字符串P所在的第一個(gè)字符處發(fā)生失配，此時(shí)j=0，所以讓目標(biāo)的指針前進(jìn)一位，模式的其實(shí)比較位置回到p0。接著進(jìn)行第三輪比較。模式串P中的第7個(gè)字符發(fā)生失配，此時(shí)j=6。可知下一輪匹配的起始比較位置為P f(6-1)+1，即p2。目標(biāo)指針不發(fā)生回溯，仍指向失配位置。接著進(jìn)行第四輪匹配，第四輪匹配成功。 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&&