資源描述：
《模式匹配kmp算法實(shí)驗(yàn)步驟》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、一、問題描述模式匹配兩個串。二、設(shè)計(jì)思想這種由D.E.Knuth,J.H.Morris和V.R.Pratt同吋發(fā)現(xiàn)的改進(jìn)的模式匹配算法簡稱為KMP算法。注意到這是一個改進(jìn)的算法，所以有必要把原來的模式匹配兌法拿出來，其實(shí)理解的關(guān)鍵就在這里，一般的匹配算法：intIndex(StringS,StringT,intpos)//參考《數(shù)據(jù)結(jié)構(gòu)》屮的程序{i=pos;j=l;//這里的屯的笫1個元素下標(biāo)是1while(i<=S.Length&&j<=T.Length){if(S[i]=T[j]){++i;++j;}eIsc{i=
2、i~j+2;j=l;}//木本*本本本*本本本*本本本(1)}if(j>T.Length)returni-T.Length;//匹配成功elsereturn0;匹配的過程非常淸晰，關(guān)鍵足當(dāng)‘失配’的吋候稅序足如何處理的？為什么要冋溯，看下面的例子：S:aaaaabababcaaaT:ababcaaaaabababcaaaababc.(.表示做一個已經(jīng)失配)回溯的結(jié)果就是aaaaabababcaaaa.(babe)如果不W溯就是aaaaabababcaaaaba.be這樣就漏了一個可能匹配成功的情況aaaaabababca
3、aaababc這是由T串本身的性質(zhì)決定的，是因?yàn)門串本身有前后’部分匹配’的性質(zhì)。如果T為abedef這樣的，人沒奮冋溯的必要。改進(jìn)的地方也就是這里，我們從T串本身出發(fā)，事先就找準(zhǔn)了TA身前后部分匹配的位置，那就可以改進(jìn)算法。如果不用W溯，那T串下一個位置從哪甩開始呢？還是上面那個例子，T為ababc,如果c失配，那就可以往前移到aba最后一個a的位置，像這樣.?…ababd…ababc->ababc這樣i不川回溯，j跳到前2個位S,繼續(xù)匹配的過程，這就是KMP算法所在。這個當(dāng)T[j]失配后，j應(yīng)該往前跳的值就是j的ne
4、xt值，它是由T串本身固有決定的，與S串無關(guān)?！稊?shù)據(jù)結(jié)構(gòu)》上給了next值的定義：0如果j=lnext[j]={Max{k
5、l〈k〈j?(!.’pi..?pk-f-pj-k+1...pj-T1其它情況-K實(shí)它就是描述前面表述的情況，關(guān)于next[l]=O是規(guī)定的，這樣規(guī)定可以使程序簡單一些，如果非要定為其它的值只要不和后面的值沖突也足可以的；而那個Max是什么意思，舉個例子:T:aaab...aaaab...aaab一〉aaab->aaab->aaab像這樣的T,前而A身部分匹配的部分不止兩個，那應(yīng)該往前跳到第幾個呢？最
6、近的一個，也就是說盡可能的向右滑移蛣短的長度。到這里，就實(shí)現(xiàn)了KMP的大部分內(nèi)容，然后關(guān)鍵的問題是如何求next值？先看如何用它來進(jìn)行匹配操作。將最前而的程序改寫成：intIndex_KMP(StringS,StringT,intpos){i=pos;j=l;//這里的中的第1個素下標(biāo)是1while(i<=S.Length&&j<=T.Length)if(j==O
7、
8、S[i]==T[j]){++i;++j;}//注意到這里的j==0,和++j的作用就知道為什么規(guī)定next[l]=O的好處了elsej=next[j];//
9、i不變(不回溯)，j跳動}if(j>T.Length)returni-T.Length;//匹配成功elsereturn0;}求next值，這也是整個算法成功的關(guān)鍵。前說過丫，next值表達(dá)的就是T申的自身部分匹配的性質(zhì)，那么，我只耍將T串和T串A身來一次匹配就可以求岀來了，這里的匹配過程不是從頭一個一個匹配，而是從T[l]和T[2]開始匹配，給出算法如下：voidget_noxt(StringT,int&next[]){i=l;j=0;next[l]=0;while(i<=T.Length){if(j==O
10、
11、T[i]
12、==T[j]){++i;++j;next[i]=j;/**********(2)*/}elsej=next[j];}}看這個函數(shù)非常像KMP匹配的函數(shù)！注意到(2)語川邏樹蒗蓋的時候是T[i]==T[j]以及i前面的、j前面的都匹配的情況不，于足先tl增，然后記下來next[i]=j，這樣每當(dāng)i宥自增就會求得一個next[i],而j一定會小子等于i，于是對于已經(jīng)求出來的next,可以繼續(xù)求后面的next,而next[l]=0是己知，所以整個就這樣遞推的求出來了，方法非常巧妙。這樣的改進(jìn)己經(jīng)是很不錯了，但算法還對以改進(jìn)，注
13、意到K而的匹配惜況：???Haac.?.ci3cia.T串中的’a’和S中中的’c’失配，而’a’的next值指的還是’a’，那同樣的比較還是會失配，而這樣的比較是多余的，如果我事先知道，當(dāng)T[i]==T[j]，那next[i]就設(shè)為nextEj],在求next值的吋候就己經(jīng)比較了，這樣就可以去掉這樣的多余的比較。于
