資源描述：
《模式匹配的KMP算法詳解》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、模式匹配的KMP算法詳解?模式匹配的KMP算法詳解這種由D.E.Knuth,J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的改進的模式匹配算法簡稱為KMP算法。大概學過信息學的都知道，是個比較難理解的算法，今天特把它搞個徹徹底底明明白白。注意到這是一個改進的算法，所以有必要把原來的模式匹配算法拿出來，其實理解的關鍵就在這里，一般的匹配算法：intIndex(StringS,StringT,intpos)//參考《數(shù)據結構》中的程序{?i=pos;j=1;//這里的串的第1個元素下標是1?while(i<=S.Length&&j<=
2、T.Length)?{???if(S[i]==T[j]){++i;++j;}???else{i=i-j+2;j=1;}//**************(1)?}?if(j>T.Length)returni-T.Length;//匹配成功?elsereturn0;}匹配的過程非常清晰，關鍵是當‘失配’的時候程序是如何處理的？回溯，沒錯，注意到(1)句，為什么要回溯，看下面的例子：S:aaaaabababcaaa?T:ababcaaaaabababcaaa???ababc.(.表示前一個已經失配)回溯的結果就是aaaaabababcaa
3、a????a.(babc)如果不回溯就是aaaaabababcaaa???????aba.bc這樣就漏了一個可能匹配成功的情況aaaaabababcaaa?????ababc為什么會發(fā)生這樣的情況？這是由T串本身的性質決定的，是因為T串本身有前后'部分匹配'的性質。如果T為abcdef這樣的，大沒有回溯的必要。改進的地方也就是這里，我們從T串本身出發(fā)，事先就找準了T自身前后部分匹配的位置，那就可以改進算法。如果不用回溯，那T串下一個位置從哪里開始呢？還是上面那個例子，T為ababc，如果c失配，那就可以往前移到aba最后一個a的位置
4、，像這樣：...ababd...??ababc??->ababc這樣i不用回溯，j跳到前2個位置，繼續(xù)匹配的過程，這就是KMP算法所在。這個當T[j]失配后，j應該往前跳的值就是j的next值，它是由T串本身固有決定的，與S串無關?！稊?shù)據結構》上給了next值的定義：?????????0??如果j=1next[j]={Max{k
5、16、簡單一些，如果非要定為其它的值只要不和后面的值沖突也是可以的；而那個Max是什么意思，舉個例子：T:aaab...aaaab...??aaab?->aaab??->aaab???->aaab像這樣的T，前面自身部分匹配的部分不止兩個，那應該往前跳到第幾個呢？最近的一個，也就是說盡可能的向右滑移最短的長度。OK，了解到這里，就看清了KMP的大部分內容，然后關鍵的問題是如何求next值？先不管它，先看如何用它來進行匹配操作，也就是說先假設已經有了next值。將最前面的程序改寫成：intIndex_KMP(StringS,StringT,
7、intpos){?i=pos;j=1;//這里的串的第1個元素下標是1?while(i<=S.Length&&j<=T.Length)?{???if(j==0
8、
9、S[i]==T[j]){++i;++j;}//注意到這里的j==0,和++j的作用就知道為什么規(guī)定next[1]=0的好處了???elsej=next[j];//i不變（不回溯）,j跳動?}?if(j>T.Length)returni-T.Length;//匹配成功?elsereturn0;}OK,是不是非常簡單？還有更簡單的，求next值，這也是整個算法成功的關鍵，從ne
10、xt值的定義來求太恐怖了，怎么求？前面說過了，next值表達的就是T串的自身部分匹配的性質，那么，我只要將T串和T串自身來一次匹配就可以求出來了，這里的匹配過程不是從頭一個一個匹配，而是從T[1]和T[2]開始匹配，給出算法如下：voidget_next(StringT,int&next[]){?i=1;j=0;next[1]=0;?while(i<=T.Length)?{???if(j==0
11、
12、T[i]==T[j]){++i;++j;next[i]=j;/**********(2)*/}???elsej=next[j];?}}看這
13、個函數(shù)是不是非常像KMP匹配的函數(shù)，沒錯，它就是這么干的！注意到(2)語句邏輯覆蓋的時候是T[i]==T[j]以及i前面的、j前面的都匹配的情況下，于是先自增，然后記下來next[i]=j，這樣每當i有自增就會求得一個next[i]，
