KMP算法和樸素算法模式匹配

《KMP算法和樸素算法模式匹配》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、KMP算法和樸素算法(后面賦有能直接運行的C語言代碼)　　現(xiàn)在討論一般情況?！　〖僭O(shè)　　主串：s:‘s(1)s(2)s(3)……s(n)’;　　模式串：p:‘p(1)p(2)p(3)…..p(m)’　　把課本上的這一段看完后，繼續(xù)　　現(xiàn)在我們假設(shè)主串第i個字符與模式串的第j(j<=m)個字符‘失配’后，主串第i個字符與模式串的第k(k

2、

3、(相配)

4、

5、≠(失配)　　匹配串：p(1)...........p(j-1)p(j)　

6、　由此，我們得到關(guān)系式：　　‘p(1)p(2)p(3)…..p(j-1)’=’s(i-j+1)……s(i-1)’　　由于s(i)≠p(j)，接下來s(i)將與p(k)繼續(xù)比較，則模式串中的前(k-1)個字符的子串必須滿足下列關(guān)系式，并且不可能存在k’>k滿足下列關(guān)系式：(k

7、

8、(相配)

9、

10、

11、

12、?(有待比較)　　匹配串：p(1)p(2)…….

13、....p(k-1)p(k)　　現(xiàn)在我們把前面總結(jié)的關(guān)系綜合一下　　有：　　s(1)…s(i-j+1)…s(i-k+1)s(i-k+2)……s(i-1)s(i)……　　

14、

15、(相配)

16、

17、

18、

19、

20、

21、≠(失配)　　p(1)……p(j-k+1)p(j-k+2)…......p(j-1)p(j)　　

22、

23、(相配)

24、

25、

26、

27、?(有待比較)　　p(1)p(2)……......p(k-1)p(k)　　由上，我們得到關(guān)系：　　'p(1)p(2)p(3)…..p(k-1)’='p(j-k+1)p(j-k+2)……p(j-1)’　　接下來看“反之，若模式串中存在滿足式(4-4

28、)。。。。。。?！边@一段?？赐赀@一段，如果下面的看不懂就不要看了。直接去看那個next函數(shù)的源程序。(偽代碼)　　K是和next有關(guān)系的，不過在最初看的時候，你不要太追究k到底是多少，至于next值是怎么求出來的，我教你怎么學(xué)會。　　課本83頁不是有個例子嗎？就是圖4.6　　你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。　　在理解上面代碼的基礎(chǔ)上，建議自己尋找一些KMP算法的練習(xí)，也可以自己寫兩個較為簡單的字符串進(jìn)行人腦模擬這種方法的練習(xí)，以加深對算法的理解。KMP算法的優(yōu)化　　KMP算法是可以被進(jìn)一步優(yōu)化

29、的?！　∥覀円砸粋€例子來說明。譬如我們給的P字符串是“abcdaabcab”，經(jīng)過KMP算法，應(yīng)當(dāng)?shù)玫健疤卣飨蛄俊比缦卤硭荆骸　∠聵?biāo)i0123456789p(i)abcdaabcabnext[i]-1000011231但是，如果此時發(fā)現(xiàn)p(i)==p(k)，那么應(yīng)當(dāng)將相應(yīng)的next[i]的值更改為next[k]的值。經(jīng)過優(yōu)化后可以得到下面的表格：　　下標(biāo)i0123456789p(i)abcdaabcabnext[i]-1000112312優(yōu)化的next[i]-1000-110030附：（以下為本人已調(diào)試通過的進(jìn)行兩種模式匹配的算法，直接復(fù)制即可運

30、行。）#include#include#defineMAXSIZE100intIndex_BF(charS[],charT[],intpos);intKMP(char*Text,char*Pattern,intpos);voidmain(){intk,pos,n;chars11[MAXSIZE];chars22[MAXSIZE];do{printf("*********************主菜單*********************");printf("1.輸入待匹配的兩個字符串");printf(

31、"2.模式匹配的樸素算法進(jìn)行匹配");printf("3.模式匹配的KMP算法進(jìn)行匹配");printf("4.結(jié)束程序");printf("請輸入您的選擇(以輸入10表結(jié)束:)");scanf("%d",&k);switch(k){case1:{printf("pleaseinputtheMAINLYstring:");scanf("%s",s11);printf("pleaseinputtheMODEstring:");scanf("%s",s22);printf("pleaseenterthepositionyouwantto

32、start:");scanf("%d",&pos);break;}case2:{n=Index_BF(s11,s22,po