使用KMP算法實(shí)現(xiàn)一個(gè)模式匹配

《使用KMP算法實(shí)現(xiàn)一個(gè)模式匹配》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、課程設(shè)計(jì)——數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目：KMP算法實(shí)現(xiàn)一個(gè)模式匹配指導(dǎo)老師：徐浩學(xué)生姓名：孫文莉班級：信122班學(xué)號：1290842272014年6月16日一、問題描述：使用KMP算法實(shí)現(xiàn)一個(gè)模式匹配用C/C++編寫一個(gè)程序?qū)崿F(xiàn)模式匹配的KMP算法。要求在一個(gè)字符串中搜索某個(gè)子串，若搜索到就返回子串的位置；若未搜索到，就返回0。首先要輸入個(gè)主串和模式串，先根據(jù)next()函數(shù)求模式串的next值，利用KMP算法進(jìn)行匹配，再用輸出函數(shù)輸出結(jié)果！二、設(shè)計(jì)思路：該算法分為五三個(gè)模塊：第一模塊[input()函數(shù)]（利用該函數(shù)輸入主串和模式串的值）；第二模塊[StrLength（）]（利用該函數(shù)求各串的長度）；

2、第三模塊[get_next()函數(shù)]（利用該函數(shù)求出模式串的next函數(shù)值）；第四模塊[Index_KM（）函數(shù)]（利用該函數(shù)進(jìn)行主串和模式串之間的匹配）；第五模塊[output()函數(shù)利用該函數(shù)輸出匹配結(jié)果）。個(gè)模塊之間的調(diào)用關(guān)系如下圖所示：圖4.1是對整個(gè)函數(shù)的流程圖。圖4.2是對KMP算法的流程圖；圖4.3是求next的函數(shù)值的流程圖。因水平有限，最終程序清單與這個(gè)流程圖不同的地方，請諒解。大致思路是一致、、、三、數(shù)據(jù)結(jié)構(gòu)定義：#defineMAXSIZE100；intindex_KMP(char*s,char*t,intpos);voidget_next(char*t,int*);用最

3、簡單的數(shù)組進(jìn)行KMP模式匹配主串：chars[10]="abcacbabb";模式串：chart[4]="cac";intnext[4];intpos=0;四、系統(tǒng)功能介紹：求模式串的模式值next[]函數(shù)用《模式匹配的KMP算法》當(dāng)主串和模式串匹配不相等是，模式串應(yīng)向右移動(dòng)一段距離，此時(shí)我們需要得到模式串的next函數(shù)值。如何求next函數(shù)，next函數(shù)值僅取決于模式本身而和主串無關(guān)。我們可以從分析next函數(shù)的定義出發(fā)用遞推的方法求得next函數(shù)值。由定義知：next[1]=0設(shè)next[j]=k，即有：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1next[j+1]=?　可

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

5、j＂此：next[j+1]=next[k]+1同理若tk′≠tj，則將模式繼續(xù)向右滑動(dòng)至使第next[k′]個(gè)字符和tj對齊，依此類推，直至tj和模式中的某個(gè)字符匹配成功或者不存在任何k′(1

6、

7、t[i]==t[j]){i++;j++;next[

8、i]=j;}elsej=next[j];}}模式匹配KMP算法的實(shí)現(xiàn)KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動(dòng)”至某個(gè)位置上，使得tk對準(zhǔn)si繼續(xù)向右進(jìn)行。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動(dòng)”到哪個(gè)位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動(dòng)，模式t向右“滑動(dòng)”，使tk和si對準(zhǔn)繼續(xù)向右進(jìn)行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：＂t1t2…tk-1＂=＂si-k+1si-k+2…si-1＂(4.1)式左邊是tk前面的k-1個(gè)字符，右邊是si前面的k-1個(gè)字符。而本趟匹配失敗是在si和tj之處，已經(jīng)得到的部分匹配結(jié)果是：＂t1t

9、2…tj-1＂=＂si-j+1si-j+2…　si-1＂（4.2）因?yàn)閗