模式匹配的KMP算法研究

1、模式匹配的KMP算法研究學(xué)生姓名：黃飛 指導(dǎo)老師：羅心摘 要 在計(jì)算機(jī)科學(xué)領(lǐng)域，串的模式匹配（以下簡(jiǎn)稱為串匹配）算法一直都是研究焦點(diǎn)之一。在拼寫(xiě)檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測(cè)、計(jì)算機(jī)病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進(jìn)行串匹配。串匹配就是在主串中查找模式串的一個(gè)或所有出現(xiàn)。在本文中主串表示為S=s1s2s3sn，模式串表示為T(mén)=t1t2tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改進(jìn)算法。本文主要在精確匹配方面對(duì)KMP算法進(jìn)行了討論并對(duì)它做一些改進(jìn)以及利用改進(jìn)的KMP來(lái)實(shí)現(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 引言對(duì)于一般的模式匹配算法：分別利用兩個(gè)指針i和j指示主串S和T中的當(dāng)前正待比較的字符位置。算法的基本思想是：從主串的S的第POS個(gè)字符開(kāi)始起和模式的第一個(gè)字符比較之，如相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從主串的下一個(gè)字符起再重新和模式的字符比較之。以此類(lèi)推，直到模式T

6、中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)字符序列相等，則稱匹配成功，則函數(shù)值為和模式T中的第一個(gè)字符相等的字符在主串S中的序號(hào)，否則稱匹配不成功，函數(shù)值為0.而對(duì)于模式匹配的KMP算法可以在O(n+m)的時(shí)間數(shù)量級(jí)上完成串的模式匹配操作。其改進(jìn)過(guò)程在于:每當(dāng)一趟匹配過(guò)程出現(xiàn)字符比較不相等時(shí)，不需回溯i指針，而是利用已經(jīng)得到的部分匹配的結(jié)果將模式串向右滑動(dòng)一段盡可能遠(yuǎn)的距離后，繼續(xù)進(jìn)行比較?；瑒?dòng)的這一段距離我們將會(huì)用到函數(shù)next, KMP算法的最大特點(diǎn)是指示主串的指針不須回溯，整個(gè)匹配過(guò)程中，對(duì)主串僅需從頭到尾掃描一遍，這對(duì)處理從外設(shè)輸入的龐大文件很有效，可以邊度入邊匹配，而無(wú)需回頭重讀。2、問(wèn)題

7、分析2.1 問(wèn)題的分析和任務(wù)的定義用C/C+編寫(xiě)一個(gè)程序?qū)崿F(xiàn)模式匹配的KMP算法。要求在一個(gè)字符串中搜索某個(gè)子串，若搜索到就返回子串的位置；若未搜索到，就返回0。 首先要輸入個(gè)主串和模式串，先根據(jù)next( )函數(shù)求模式串的next值，利用KMP 算法進(jìn)行匹配，再用輸出函數(shù)輸出結(jié)果！2.2 設(shè)計(jì)過(guò)程本次課程設(shè)計(jì)利用模式匹配KMP算法實(shí)現(xiàn)串的相關(guān)操作：分別從鍵盤(pán)上任意輸入三組字符串作為主串，在任意數(shù)取三組字符串作為模式串，利用模式匹配KMP算法依次使三組模式串與三組主串匹配，在使用模式匹配KMP算法時(shí)會(huì)調(diào)用到Getnext()函數(shù)。2.3 邏輯設(shè)計(jì)對(duì)該kmp 算法，定義的抽象數(shù)據(jù)類(lèi)型如下：ADT

8、 String 數(shù)據(jù)對(duì)象：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é)果：生成一個(gè)其值等于chars的串T。 StrCopy（S）初始條件：串S存在。操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。 StrLength(S)初始條件：串S存在。操作結(jié)果：返回S元素的個(gè)數(shù)，成為串的長(zhǎng)度。 Index(S,T,pos)初始條件：串S和T存在，T是非空串，1posStrLength(S).操作結(jié)

9、果：若主串S中存在和串T相同的子串，則返回他在主串S中的第pos個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。 DestoryString(&S)初始條件：串S存在。操作結(jié)果：串S被銷(xiāo)毀。ADT String 該算法是對(duì)進(jìn)行操作，對(duì)串的存儲(chǔ)結(jié)構(gòu)用定長(zhǎng)順序存儲(chǔ)表示：類(lèi)似于現(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值得字符序列。在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)中，按照與定義大小，為每個(gè)定義的串分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)，則可用定長(zhǎng)數(shù)組如下描述。 #define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1該算法分為五三個(gè)模塊：第一模

10、塊StrLength（）（利用該函數(shù)求各串的長(zhǎng)度）；第二模塊input( )函數(shù)（利用該函數(shù)輸入主串和模式串的值）；第三模塊get_next( )函數(shù)（利用該函數(shù)求出模式串的next函數(shù)值）；第四模塊Index_KM（）函數(shù)（利用該函數(shù)進(jìn)行主串和模式串之間的匹配）；第五模塊output( )函數(shù)利用該函數(shù)輸出匹配結(jié)果）。個(gè)模塊之間的調(diào)用關(guān)系如下圖所示：圖4.1是對(duì)整個(gè)函數(shù)的流程圖。圖4.2是對(duì)KMP算法的流程圖；圖4.3是求next的函數(shù)值的流程圖。圖2.1模塊調(diào)用流程圖3、解決方案3.1 為主串和模式串賦值分別定義三組字符串作為主串str1,str2,str3,利用cin函數(shù)依次為為三組字符

11、串賦值，從鍵盤(pán)上任意輸入字符分別賦給str1 str2 str3,;以同樣的方法模模式串p1,p2,p3賦值。3.2 求各串的長(zhǎng)度StrLength（）函數(shù)求的各串的長(zhǎng)度，利用一個(gè)while循環(huán)語(yǔ)句，為后面的函數(shù)做好準(zhǔn)備工作。3.3 求模式串的模式值next函數(shù)用模式匹配的KMP算法當(dāng)主串和模式串匹配不相等是，模式串應(yīng)向右移動(dòng)一段距離，此時(shí)我們需要得到模式串的next函數(shù)值。 如何求next函數(shù)，next函數(shù)值僅取決于模式本身而和主串無(wú)關(guān)。我們可以從分析next函數(shù)的定義出發(fā)用遞推的方法求得next函數(shù)值。由定義知：next1=0設(shè)nextj=k，即有：t1 t2 tk-1 =tj-k+1 t

12、j-k+2 tj-1 nextj+1=?可能有兩種情況：一種情況：若tk tj 則表明在模式串中這就是說(shuō)nextj+1=k+1，即nextj=nextj+1 第二種情況：若tk tj 則表明在模式串中t1 t2 tk tj-k+1 tj-k+2 tj 此時(shí)可把求next函數(shù)值的問(wèn)題看成是一個(gè)模式匹配問(wèn)題，整個(gè)模式串既是主串又是模式，而當(dāng)前在匹配的過(guò)程中，已有(4.6)式成立，則當(dāng)tk tj 時(shí)應(yīng)將模式向右滑動(dòng)，使得第nextk個(gè)字符和“主串”中的第j個(gè)字符相比較。若nextk=k，且t ktj，則說(shuō)明在主串中第j+1個(gè)字符之前存在一個(gè)最大長(zhǎng)度為k的子串，使得t1 t2 t k =tj-k+1

13、tj- k+2 tj 此： nextj+1=nextk+1 同理若t k tj，則將模式繼續(xù)向右滑動(dòng)至使第nextk個(gè)字符和tj 對(duì)齊，依此類(lèi)推，直至tj 和模式中的某個(gè)字符匹配成功或者不存在任何 k(1< k<k <<j)滿足，此時(shí)若t1tj+1 ， 則有：nextj+1=1 否則若t1=tj+1 ，則有：nextj+1=0 綜上所述，求next函數(shù)值過(guò)程的算法如下：void get _next(char t,int next )/*求模式t的next值并寸入next數(shù)組中*/ int i=1,j=0;next0=0;while (i<t0) while (j=

14、0|ti-1 = =tj-1) +i;+j;nexti-1=j; else j=nextj-1;/get_next3.4 模式匹配KMP算法的實(shí)現(xiàn)KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動(dòng)”至某個(gè)位置上，使得tk 對(duì)準(zhǔn) s i 繼續(xù)向右進(jìn)行。顯然，現(xiàn)在問(wèn)題的關(guān)鍵是串t“滑動(dòng)”到哪個(gè)位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動(dòng)，模式t向右“滑動(dòng)”，使tk和si對(duì)準(zhǔn)繼續(xù)向右進(jìn)行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：t1 t2 tk-1 =si-k+1 si-k+2 si-1 (4.1)式左邊是tk前面的k-1個(gè)字符，右邊是si

15、前面的k-1個(gè)字符。而本趟匹配失敗是在si和tj之處，已經(jīng)得到的部分匹配結(jié)果是：t1 t2 tj-1 =si-j+1 si-j+2 si-1 （4.2）因?yàn)閗<j，所以有：tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (4.3)式左邊是 tj前面的k-1個(gè)字符，右邊是si 前面的k-1個(gè)字符，通過(guò)(4.1)和(4.3)得到關(guān)系：t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 (4.4)結(jié)論：某趟在si和tj匹配失敗后，如果模式串中有滿足關(guān)系(4)的子串存在，即：模式中的前k-1個(gè)字符與模式中tj字符前面的k-1個(gè)字符相等時(shí)，模式t就可以向右“

16、滑動(dòng)”至使tk和si對(duì)準(zhǔn)，繼續(xù)向右進(jìn)行比較即可。在求得模式的next函數(shù)之后，匹配可如下進(jìn)行：假設(shè)以指針i和j分別指示主串和模式中的比較字符，令i的初值為pos，j的初值為1。若在匹配過(guò)程中sitj，則i和j分別增，若sitj 匹配失敗后，則i不變，j退到nextj位置再比較，若相等，則指針各自增，否則j再退到下一個(gè)next值的位置，依此類(lèi)推。直至下列兩種情況：一種是j退到某個(gè)next值時(shí)字符比較相等，則i和j分別增繼續(xù)進(jìn)行匹配; 另一種是j退到值為零（即模式的第一個(gè)字符失配），則此時(shí)i和j也要分別增，表明從主串的下一個(gè)字符起和模式重新開(kāi)始匹配。KMP算法如下：int StrIndex_KMP

17、(char *s,char *t,int pos)/*從串s的第pos個(gè)字符開(kāi)始找首次與串t相等的子串*/ int i=pos,j=-1,slen,tlen;while (i<=s0 && j<=t0 ) /*都沒(méi)遇到結(jié)束符*/if (j=-1|s=tj) i+; j+; else j=nextj-1; /*回溯*/if (j>t0) return i-t0+1;/*匹配成功，返回存儲(chǔ)位置*/else return 04程序調(diào)試與測(cè)試4.1 若匹配成功：調(diào)試結(jié)果如下圖所示圖4.1 匹配成功4.2 若匹配不成功：調(diào)試結(jié)果如下所示圖4.2 匹配不成功4.3 結(jié)果分

18、析利用該程序求模式串是否可以在主串中找到，先利用next( )函數(shù)求的模式串的next 函數(shù)值，利用for 循環(huán)語(yǔ)句分別輸出next 函數(shù)值：（0，1，2，3，4）；（0，1，2，3）（0，1，1，2，2，3，1，2），再用KMP算法進(jìn)行查找，若查找成功則輸出模式串在主串中的位置:9 ,8, 9. 若沒(méi)有找到則返回0；該調(diào)試結(jié)果與程序相對(duì)應(yīng)；對(duì)于模式匹配KMP算法時(shí)間復(fù)雜度為O（n+m）;對(duì)于next( )函數(shù)的時(shí)間復(fù)雜度為O（m）其中n表示主串的長(zhǎng)度，m表示子串的長(zhǎng)度。5 結(jié)束語(yǔ)在這次課程設(shè)計(jì)中，我做的一個(gè)簡(jiǎn)單的模式匹配的kmp的算法，該算法是對(duì)一般算法的改進(jìn)，kmp算法僅當(dāng)模式與主串之間存

19、在部分匹配時(shí)才比一般模式匹配算法快。其次該算法的最大特點(diǎn)是，指示主串的指針不需回溯，整個(gè)匹配過(guò)程中，對(duì)主串僅需要從頭到尾掃描一遍，這時(shí)處理從外設(shè)輸入的龐大文件有很大的效果，可以邊輸入邊匹配，而無(wú)需回頭讀。 剛開(kāi)始，對(duì)求子串的next值時(shí)，我僅對(duì)一串字符進(jìn)行實(shí)例說(shuō)明，經(jīng)過(guò)自己和組員的討論，我們共同研究才開(kāi)始理解了該算法的應(yīng)用，。讓我們體驗(yàn)到了“過(guò)程是完美的”；正如 一句話所說(shuō)的，“我們可以 錯(cuò)過(guò)一路風(fēng)景，但不能錯(cuò)過(guò)終點(diǎn)站”我將之改為“我可以不在乎結(jié)果，但我們永遠(yuǎn)記得過(guò)程最美”。一個(gè)好的程序=好結(jié)構(gòu)+好結(jié)構(gòu)，這次課設(shè)真讓我體驗(yàn)到這句話。當(dāng)然，通過(guò)這次課程設(shè)計(jì)，我也發(fā)現(xiàn)了自身的很多不足之處，在以后的

20、學(xué)習(xí)中，我會(huì)不斷的完善自我，不斷進(jìn)取，能使自己在編程這方面有一個(gè)大的發(fā)展。在以后的工作中，我會(huì)彌補(bǔ)自己在設(shè)計(jì)方面的不足。在工作中，學(xué)會(huì)合作。其次，謝謝老師，學(xué)校給我提供的這次機(jī)會(huì)！參考文獻(xiàn)1 嚴(yán)蔚敏 吳偉民數(shù)據(jù)結(jié)構(gòu)2 王宏生 宋繼紅數(shù)據(jù)結(jié)構(gòu)3 彭波數(shù)據(jù)結(jié)構(gòu)教程4 5 陳杰計(jì)算機(jī)專業(yè)課程設(shè)計(jì)中的需求分析J集美大學(xué)學(xué)報(bào).20096 高一凡數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析M 西安.西安電子科技大學(xué)出版社. 20027 黃國(guó)瑜 葉乃箐數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）附錄： 程序清單# include"iostream.h"# include "string"# include&quo

21、t;stdlib.h"#define MaxStrLen 200char s1MaxStrLen,s2MaxStrLen,s3MaxStrLen,p120,p220,p320;int next20;int StrLength(char* s);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') l

22、en+=1;i+;return len;void input() /利用該函數(shù)為串賦值。cout<<"please input the main string of S1:n"cin>>s1;cout<<"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

23、 sub string of p1:n"cin>>p1;cout<<"please input the sub string of p2:n"cin>>p2;cout<<"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個(gè)字符后的位置;/串s和t采用定長(zhǎng)順序存儲(chǔ),且t非空,1<=pos<=strlent(s)-strlent(t)+1.int i,j,ls,lt;i=pos-1,j=-1;/設(shè)置初值ls=StrLength(s); /求主串s的長(zhǎng)度lt=StrLength(t);/求模式串t的長(zhǎng)度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;/匹配不成功void get_n