模式匹配KMP算法實(shí)驗(yàn)報告

1、實(shí)驗(yàn)四：KMP算法實(shí)驗(yàn)報告一、 問題描述模式匹配兩個串。二、 設(shè)計思想這種由D.E.Knuth,J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的改進(jìn)的模式匹配算法簡稱為KMP算法。注意到這是一個改進(jìn)的算法，所以有必要把原來的模式匹配算法拿出來，其實(shí)理解的關(guān)鍵就在這里，一般的匹配算法：int Index(String S,String T,int pos)/參考數(shù)據(jù)結(jié)構(gòu)中的程序 i=pos;j=1;/這里的串的第1個元素下標(biāo)是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配成功 else return 0;匹配的過程非常清晰，關(guān)鍵是當(dāng)失

2、配的時候程序是如何處理的？為什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaa ababc.(.表示前一個已經(jīng)失配)回溯的結(jié)果就是aaaaabababcaaa a.(babc)如果不回溯就是aaaaabababcaaa aba.bc這樣就漏了一個可能匹配成功的情況aaaaabababcaaa ababc這是由T串本身的性質(zhì)決定的，是因?yàn)門串本身有前后部分匹配的性質(zhì)。如果T為abcdef這樣的，大沒有回溯的必要。改進(jìn)的地方也就是這里，我們從T串本身出發(fā)，事先就找準(zhǔn)了T自身前后部分匹配的位置，那就可以改進(jìn)算法。如果不用回溯，那T串下一個位置從哪里

3、開始呢？還是上面那個例子，T為ababc，如果c失配，那就可以往前移到aba最后一個a的位置，像這樣：.ababd. ababc -ababc這樣i不用回溯，j跳到前2個位置，繼續(xù)匹配的過程，這就是KMP算法所在。這個當(dāng)Tj失配后，j應(yīng)該往前跳的值就是j的next值，它是由T串本身固有決定的，與S串無關(guān)。數(shù)據(jù)結(jié)構(gòu)上給了next值的定義： 0 如果j=1 nextj=Maxk|1kaaab -aaab -aaab像這樣的T，前面自身部分匹配的部分不止兩個，那應(yīng)該往前跳到第幾個呢？最近的一個，也就是說盡可能的向右滑移最短的長度。到這里，就實(shí)現(xiàn)了KMP的大部分內(nèi)容，然后關(guān)鍵的問題是如何求next值？

4、先看如何用它來進(jìn)行匹配操作。將最前面的程序改寫成：int Index_KMP(String S,String T,int pos) i=pos;j=1;/這里的串的第1個元素下標(biāo)是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配成功 else return 0;求next值，這也是整個算法成功的關(guān)鍵。前面說過了，next值表達(dá)的就是T串的自身部分匹配的性質(zhì)，那么，我只要將T串和T串自身來一次匹配就可以求出來了，這里的匹配過程不是從頭一個一個匹配，而是從T1和T2開始匹配，給出算法如下：void get_next(String T,int

5、 &next) i=1;j=0;next1=0; while(i=T.Length) if(j=0 | Ti=Tj)+i;+j; nexti=j;/*(2)*/ else j=nextj; 看這個函數(shù)非常像KMP匹配的函數(shù)！注意到(2)語句邏輯覆蓋的時候是Ti=Tj以及i前面的、j前面的都匹配的情況下，于是先自增，然后記下來nexti=j，這樣每當(dāng)i有自增就會求得一個nexti，而j一定會小于等于i，于是對于已經(jīng)求出來的next，可以繼續(xù)求后面的next，而next1=0是已知，所以整個就這樣遞推的求出來了，方法非常巧妙。這樣的改進(jìn)已經(jīng)是很不錯了，但算法還可以改進(jìn)，注意到下面的匹配情況：.aa

6、ac. aaaa. T串中的a和S串中的c失配，而a的next值指的還是a，那同樣的比較還是會失配，而這樣的比較是多余的，如果我事先知道，當(dāng)Ti=Tj，那nexti就設(shè)為nextj，在求next值的時候就已經(jīng)比較了，這樣就可以去掉這樣的多余的比較。于是稍加改進(jìn)得到：void get_nextval(String T,int &next) i=1;j=0;next1=0; while(i=T.Length) if(j=0 | Ti=Tj) +i;+j; if(Ti!=Tj) nexti=j; else nexti=nextj;/消去多余的可能的比較,next再向前跳 else j=nextj;

7、三、 分析理論時間復(fù)雜性這個程序或許比想像中的要簡單，因?yàn)閷τ趇值的不斷增加，代碼用的是for循環(huán)。因此，這個代碼可以這樣形象地理解：掃描字符串S，并更新可以匹配到T的什么位置。為什么這個程序是O(n)的？ KMP的時間復(fù)雜度分析可謂攤還分析的典型。我們從上述程序的j 值入手。每一次執(zhí)行while循環(huán)都會使j減小（但不能減成負(fù)的），而另外的改變j值的地方只有第五行。每次執(zhí)行了這一行，j都只能加1；因此，整個過程中j最多加了n個1。于是，j最多只有n次減小的機(jī)會（j值減小的次數(shù)當(dāng)然不能超過n，因?yàn)閖永遠(yuǎn)是非負(fù)整數(shù)）。這告訴我們，while循環(huán)總共最多執(zhí)行了n次。按照攤還分析的說法，平攤到每次fo

8、r循環(huán)后，一次for循環(huán)的復(fù)雜度為O(1)。整個過程顯然是O(n)的。這樣的分析對于后面P數(shù)組預(yù)處理的過程同樣有效，同樣可以得到預(yù)處理過程的復(fù)雜度為O(m)。四、 原程序和調(diào)試結(jié)果package kmp;public class kmp String s=aaaaaaaa; String p=aaaab; int next=new ints.length(); /主要計算next的值 void calnext() int i,j=0; next1 = 0; next0=-1; for(i=2;is.length();i+) if(s.charAt(j)=s.charAt(i-1) nexti=nexti-1+1;j+; else if(nextj0) nexti=0; else nexti=nextj; j=nexti; /輸出實(shí)際運(yùn)算次數(shù) void display() int i=0,j=0,v; int count=0; while(is.length()&jp.length() if(s.charAt(i)=p.charAt(j) i+;j+; else if(j=0)i+; else j=nextj; count+; System.out.println(+count);