模式匹配的KMP算法研究

1、模式匹配的KMP算法研究學(xué)生姓名：黃飛 指導(dǎo)老師：羅心摘 要 在計算機科學(xué)領(lǐng)域，串的模式匹配（以下簡稱為串匹配）算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進行串匹配。串匹配就是在主串中查找模式串的一個或所有出現(xiàn)。在本文中主串表示為S=s1s2s3sn，模式串表示為T=t1t2tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改進算法。本文主要在精確匹配方面對KMP算法進行了討論并對它做一些改進以及利用改進的KMP來實現(xiàn)多次模式匹配。 關(guān)鍵字：

2、模式匹配；主串；模式串；KMP算法 Research and Analysis of KMP Pattern Matching AlgorithmStudent:Huangfei Teacher:Luoxin Abstract In computer science, String pattern matching(Hereinafter referred to as the string matching) algorithm is always the focus of the study. In the spell check, language translation, data co

3、mpression, search engine, the network intrusion detection system, a computer virus signature matching DNA sequences and the application in the match, matched to string matching. String matching is in search of a string of pattern or all appear. In this paper, the string is S = s1s2s3. Sn, string pat

4、tern for T = t1t2. tm. String matching way can be divided from the accurate matching, fuzzy matching, parallel matching etc., the famous matching algorithms are KMP algorithm, BF algorithm, the algorithm and some BM algorithm. This paper in precise KMP algorithm for matching aspects are discussed an

5、d some improvement on it and using the improved KMP to realize the multiple pattern matching.Key words: pattern matching, The string; Pattern strings;KMP algorithm1 引言KMP算法是是對一般模式匹配算法的改進，由D.E.Knuth與V.R.Pratt和J.H.Morris 同時發(fā)現(xiàn)的因此人們稱它為克努特-莫里斯-莫拉特操作（簡稱為KMP算法）。對于一般的模式匹配算法：分別利用兩個指針i和j指示主串S和T中的當(dāng)前正待比較的字符位置。算

6、法的基本思想是：從主串的S的第POS個字符開始起和模式的第一個字符比較之，如相等，則繼續(xù)逐個比較后續(xù)字符；否則從主串的下一個字符起再重新和模式的字符比較之。以此類推，直到模式T中的每個字符依次和主串S中的一個連續(xù)字符序列相等，則稱匹配成功，則函數(shù)值為和模式T中的第一個字符相等的字符在主串S中的序號，否則稱匹配不成功，函數(shù)值為0.而對于模式匹配的KMP算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。其改進過程在于:每當(dāng)一趟匹配過程出現(xiàn)字符比較不相等時，不需回溯i指針，而是利用已經(jīng)得到的部分匹配的結(jié)果將模式串向右滑動一段盡可能遠(yuǎn)的距離后，繼續(xù)進行比較?；瑒拥倪@一段距離我們將會用到函數(shù)ne

7、xt, KMP算法的最大特點是指示主串的指針不須回溯，整個匹配過程中，對主串僅需從頭到尾掃描一遍，這對處理從外設(shè)輸入的龐大文件很有效，可以邊度入邊匹配，而無需回頭重讀。2、問題分析2.1 問題的分析和任務(wù)的定義用C/C+編寫一個程序?qū)崿F(xiàn)模式匹配的KMP算法。要求在一個字符串中搜索某個子串，若搜索到就返回子串的位置；若未搜索到，就返回0。 首先要輸入個主串和模式串，先根據(jù)next( )函數(shù)求模式串的next值，利用KMP 算法進行匹配，再用輸出函數(shù)輸出結(jié)果！2.2 設(shè)計過程本次課程設(shè)計利用模式匹配KMP算法實現(xiàn)串的相關(guān)操作：分別從鍵盤上任意輸入三組字符串作為主串，在任意數(shù)取三組字符串作為模式串，

8、利用模式匹配KMP算法依次使三組模式串與三組主串匹配，在使用模式匹配KMP算法時會調(diào)用到Getnext()函數(shù)。2.3 邏輯設(shè)計對該kmp 算法，定義的抽象數(shù)據(jù)類型如下：ADT String 數(shù)據(jù)對象：D=ai|aiCharacterSet,i=1,2,3,n,n0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n 基本操作：StrAssign(&T,chars) 初始條件：chars是字符串常量。操作結(jié)果：生成一個其值等于chars的串T。 StrCopy（S）初始條件：串S存在。操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。 StrLengt

9、h(S)初始條件：串S存在。操作結(jié)果：返回S元素的個數(shù)，成為串的長度。 Index(S,T,pos)初始條件：串S和T存在，T是非空串，1posStrLength(S).操作結(jié)果：若主串S中存在和串T相同的子串，則返回他在主串S中的第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。 DestoryString(&S)初始條件：串S存在。操作結(jié)果：串S被銷毀。ADT String 該算法是對進行操作，對串的存儲結(jié)構(gòu)用定長順序存儲表示：類似于現(xiàn)性表的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元存儲串值得字符序列。在串的定長順序存儲結(jié)構(gòu)中，按照與定義大小，為每個定義的串分配一個固定長度的存儲區(qū)，

10、則可用定長數(shù)組如下描述。 #define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1該算法分為五三個模塊：第一模塊StrLength（）（利用該函數(shù)求各串的長度）；第二模塊input( )函數(shù)（利用該函數(shù)輸入主串和模式串的值）；第三模塊get_next( )函數(shù)（利用該函數(shù)求出模式串的next函數(shù)值）；第四模塊Index_KM（）函數(shù)（利用該函數(shù)進行主串和模式串之間的匹配）；第五模塊output( )函數(shù)利用該函數(shù)輸出匹配結(jié)果）。個模塊之間的調(diào)用關(guān)系如下圖所示：圖4.1是對整個函數(shù)的流程圖。圖4.2是對KMP算法的流程圖；圖4.3

11、是求next的函數(shù)值的流程圖。圖2.1模塊調(diào)用流程圖3、解決方案3.1 為主串和模式串賦值分別定義三組字符串作為主串str1,str2,str3,利用cin函數(shù)依次為為三組字符串賦值，從鍵盤上任意輸入字符分別賦給str1 str2 str3,;以同樣的方法模模式串p1,p2,p3賦值。3.2 求各串的長度StrLength（）函數(shù)求的各串的長度，利用一個while循環(huán)語句，為后面的函數(shù)做好準(zhǔn)備工作。3.3 求模式串的模式值next函數(shù)用模式匹配的KMP算法當(dāng)主串和模式串匹配不相等是，模式串應(yīng)向右移動一段距離，此時我們需要得到模式串的next函數(shù)值。 如何求next函數(shù)，next函數(shù)值僅取決于模

12、式本身而和主串無關(guān)。我們可以從分析next函數(shù)的定義出發(fā)用遞推的方法求得next函數(shù)值。由定義知：next1=0設(shè)nextj=k，即有：t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 nextj+1=?可能有兩種情況：一種情況：若tk tj 則表明在模式串中這就是說nextj+1=k+1，即nextj=nextj+1 第二種情況：若tk tj 則表明在模式串中t1 t2 tk tj-k+1 tj-k+2 tj 此時可把求next函數(shù)值的問題看成是一個模式匹配問題，整個模式串既是主串又是模式，而當(dāng)前在匹配的過程中，已有(4.6)式成立，則當(dāng)tk tj 時應(yīng)將模式向右滑動，使得第ne

13、xtk個字符和“主串”中的第j個字符相比較。若nextk=k，且t ktj，則說明在主串中第j+1個字符之前存在一個最大長度為k的子串，使得t1 t2 t k =tj-k+1 tj- k+2 tj 此： nextj+1=nextk+1 同理若t k tj，則將模式繼續(xù)向右滑動至使第nextk個字符和tj 對齊，依此類推，直至tj 和模式中的某個字符匹配成功或者不存在任何 k(1< k<k <<j)滿足，此時若t1tj+1 ， 則有：nextj+1=1 否則若t1=tj+1 ，則有：nextj+1=0 綜上所述，求next函數(shù)值過程的算法如下：void get _next

14、(char t,int next )/*求模式t的next值并寸入next數(shù)組中*/ int i=1,j=0;next0=0;while (i<t0) while (j=0|ti-1 = =tj-1) +i;+j;nexti-1=j; else j=nextj-1;/get_next3.4 模式匹配KMP算法的實現(xiàn)KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動”至某個位置上，使得tk 對準(zhǔn) s i 繼續(xù)向右進行。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動”到哪個位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動，模式t向右“滑動”，使tk和s

15、i對準(zhǔn)繼續(xù)向右進行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：t1 t2 tk-1 =si-k+1 si-k+2 si-1 (4.1)式左邊是tk前面的k-1個字符，右邊是si 前面的k-1個字符。而本趟匹配失敗是在si和tj之處，已經(jīng)得到的部分匹配結(jié)果是：t1 t2 tj-1 =si-j+1 si-j+2 si-1 （4.2）因為k<j，所以有：tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (4.3)式左邊是 tj前面的k-1個字符，右邊是si 前面的k-1個字符，通過(4.1)和(4.3)得到關(guān)系：t1 t2 tk-1 =tj-k+1 tj-k+2 tj

16、-1 (4.4)結(jié)論：某趟在si和tj匹配失敗后，如果模式串中有滿足關(guān)系(4)的子串存在，即：模式中的前k-1個字符與模式中tj字符前面的k-1個字符相等時，模式t就可以向右“滑動”至使tk和si對準(zhǔn)，繼續(xù)向右進行比較即可。在求得模式的next函數(shù)之后，匹配可如下進行：假設(shè)以指針i和j分別指示主串和模式中的比較字符，令i的初值為pos，j的初值為1。若在匹配過程中sitj，則i和j分別增，若sitj 匹配失敗后，則i不變，j退到nextj位置再比較，若相等，則指針各自增，否則j再退到下一個next值的位置，依此類推。直至下列兩種情況：一種是j退到某個next值時字符比較相等，則i和j分別增繼續(xù)

17、進行匹配; 另一種是j退到值為零（即模式的第一個字符失配），則此時i和j也要分別增，表明從主串的下一個字符起和模式重新開始匹配。KMP算法如下：int StrIndex_KMP(char *s,char *t,int pos)/*從串s的第pos個字符開始找首次與串t相等的子串*/ int i=pos,j=-1,slen,tlen;while (i<=s0 && j<=t0 ) /*都沒遇到結(jié)束符*/if (j=-1|s=tj) i+; j+; else j=nextj-1; /*回溯*/if (j>t0) return i-t0+1;/*匹配成功，返回存儲位

18、置*/else return 04程序調(diào)試與測試4.1 若匹配成功：調(diào)試結(jié)果如下圖所示圖4.1 匹配成功4.2 若匹配不成功：調(diào)試結(jié)果如下所示圖4.2 匹配不成功4.3 結(jié)果分析利用該程序求模式串是否可以在主串中找到，先利用next( )函數(shù)求的模式串的next 函數(shù)值，利用for 循環(huán)語句分別輸出next 函數(shù)值：（0，1，2，3，4）；（0，1，2，3）（0，1，1，2，2，3，1，2），再用KMP算法進行查找，若查找成功則輸出模式串在主串中的位置:9 ,8, 9. 若沒有找到則返回0；該調(diào)試結(jié)果與程序相對應(yīng)；對于模式匹配KMP算法時間復(fù)雜度為O（n+m）;對于next( )函數(shù)的時間復(fù)雜

19、度為O（m）其中n表示主串的長度，m表示子串的長度。5 結(jié)束語在這次課程設(shè)計中，我做的一個簡單的模式匹配的kmp的算法，該算法是對一般算法的改進，kmp算法僅當(dāng)模式與主串之間存在部分匹配時才比一般模式匹配算法快。其次該算法的最大特點是，指示主串的指針不需回溯，整個匹配過程中，對主串僅需要從頭到尾掃描一遍，這時處理從外設(shè)輸入的龐大文件有很大的效果，可以邊輸入邊匹配，而無需回頭讀。 剛開始，對求子串的next值時，我僅對一串字符進行實例說明，經(jīng)過自己和組員的討論，我們共同研究才開始理解了該算法的應(yīng)用，。讓我們體驗到了“過程是完美的”；正如 一句話所說的，“我們可以 錯過一路風(fēng)景，但不能錯過終點站”

20、我將之改為“我可以不在乎結(jié)果，但我們永遠(yuǎn)記得過程最美”。一個好的程序=好結(jié)構(gòu)+好結(jié)構(gòu)，這次課設(shè)真讓我體驗到這句話。當(dāng)然，通過這次課程設(shè)計，我也發(fā)現(xiàn)了自身的很多不足之處，在以后的學(xué)習(xí)中，我會不斷的完善自我，不斷進取，能使自己在編程這方面有一個大的發(fā)展。在以后的工作中，我會彌補自己在設(shè)計方面的不足。在工作中，學(xué)會合作。其次，謝謝老師，學(xué)校給我提供的這次機會！參考文獻1 嚴(yán)蔚敏 吳偉民數(shù)據(jù)結(jié)構(gòu)（c語言版）北京.清華出版社.20082 王宏生 宋繼紅數(shù)據(jù)結(jié)構(gòu)北京.國防工業(yè)出版社.20063 彭波數(shù)據(jù)結(jié)構(gòu)教程北京.清華出版社.20044 譚浩強c+程序設(shè)計北京.清華大學(xué)出版社.20085 陳杰計算機專業(yè)

21、課程設(shè)計中的需求分析J集美大學(xué)學(xué)報.20096 高一凡數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析M 西安.西安電子科技大學(xué)出版社. 20027 黃國瑜 葉乃箐數(shù)據(jù)結(jié)構(gòu)（c語言版）北京.清華大學(xué)出版社.2001附錄： 程序清單# include"iostream.h"# include "string"# include"stdlib.h"#define MaxStrLen 200char s1MaxStrLen,s2MaxStrLen,s3MaxStrLen,p120,p220,p320;int next20;int StrLength(char* s)

22、;void input();int Index_KMP(char* s,char* t,int pos,int next);void get_next(char* s,int next);void output();int StrLength(char* s)int i,len;i=0;len=0;while(si!='0') len+=1;i+;return len;void input() /利用該函數(shù)為串賦值。cout<<"please input the main string of S1:n"cin>>s1;cout<

23、<"please input the main string of S2:n"cin>>s2;cout<<"please input the main string of S3:n"cin>>s3;cout<<"please input the sub string of p1:n"cin>>p1;cout<<"please input the sub string of p2:n"cin>>p2;cout<<&q

24、uot;please input the sub string of p3:n"cin>>p3; int Index_KMP(char* s,char* t,int pos,int next)/利用模式t的next函數(shù)求主串 s中的第pos個字符后的位置;/串s和t采用定長順序存儲,且t非空,1<=pos<=strlent(s)-strlent(t)+1.int i,j,ls,lt;i=pos-1,j=-1;/設(shè)置初值ls=StrLength(s); /求主串s的長度lt=StrLength(t);/求模式串t的長度while(i<ls && j<lt) if(j=-1 | si=tj) /繼續(xù)比較后繼字符 i+; j+; else j=nextj-1; /模式串向右移 if (j>=lt) return i-lt+1;/匹配成功else return 0