Posted on 2006-10-10 21:29
oyjpart 閱讀(7471)
評論(3) 編輯 收藏 引用
KMP算法是由
Knuth, Morris, Pratt三位牛人提出的快速匹配算法 得到了非常的廣泛的應(yīng)用
鑒于最近教材正在學(xué)KMP算法 我在此對次算法進行一下簡略分析 不清楚的同學(xué)可以參考一下
//By Optimistic
說明：字符串查找中，被查找的叫做目標(biāo)串，查找的叫模式串。如：
????????????目標(biāo)串：T[] = 01001010100001 模式串 P[] = 1010
算法來源: 樸素的匹配效率太低。考慮改進：1.當(dāng)模式串與目標(biāo)串在i位置比較不同時，下一個應(yīng)該從目標(biāo)串的哪里開始比較？2。下一個應(yīng)該從模式串的哪個開始比較？
于是經(jīng)過一些簡單的邏輯推理 我們得到了KMP算法的思想 讓目標(biāo)串沒有回溯 并且模式串盡可能向后滑動
我們用next[i]這個數(shù)組來存儲當(dāng)模式串的第i位比較出現(xiàn)不匹配時 模式串的從哪里開始比較
比如next[i] = 2 相當(dāng)于從從P[2]開始比較 如果next[i] = -1 代表模式串的第一個與目標(biāo)串的下一個比較
KMP的算法的精華就在于對next[i]的求取，采用next[i-1]=>next[i]的方法求得next[i]的值
下面我們來看看next[i]的求取
string str;
cin >> str;
int * next =?new int[str.length()+1];
?int i = 0, j = -1;
?next[0] = -1;
?while(i < str.length())
?{
??while(j>=0 && str[i]!=str[j])
???j = next[j];
??i++;
??j++;
??if(str[i] == str[j]) //修正
???next[i] = next[j];
??else next[i] = j;
}
其中具體的細(xì)節(jié)其參考 我同寢室同學(xué)寫的KMP算法詳解：
http://www.shnenglu.com/warrior0032/archive/2006/10/10/13543.html其中解釋了算法的基本思想和實現(xiàn)過程
我對此算法作幾個分析：
1。為什么要修正next[i]值？為什么只要修正一次？當(dāng)我們分析到模式串中的第i位于目標(biāo)串不同時 求得應(yīng)該從K位開始比較 但是如果第K位于第I位相同的時候 第K位一定與目標(biāo)串也不同因此應(yīng)該再次改成當(dāng)K位比較不同時的NEXT值 即 NEXT[K]
由于NEXT是由左向右推出來的 所以只需修正一次 (數(shù)學(xué)歸納法？呵呵。。。）
2。程序沒有使用一個數(shù)組來保存未修正時的NEXT值 而直接用J來充當(dāng)這個功能 但是J是由NEXT（已修正）得來的 那么有沒有可能J得不到正確的值？這個問題最先是我自己想的 后來驗證了一下 J一定能夠得到正確的值
下面我們來分析一下
下標(biāo)???????????????????????? 0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11 1213
目標(biāo)串???????????????????? 0? 1 ?0? 0 ?1? 0? 1? 0? 1? 0? 0?? 0?? 0??1
j(未修正的next)?????? -1 0? 0? 1? 1? 2? 3? 2? 3? 2? 3? ?4?? 1? 1
修正了的next????????? -1 0 -1? 1? 0?-1? 3 -1 3 -1? 0? 4?? 1?? 0讓我們看看但模式串比較到了12位的時候（下標(biāo)為11）
next[11] = 4; next[4] = 0; j|4 = 1...
這時候next[4]拿到的并不是正確的J值！！！
這會導(dǎo)致什么？會導(dǎo)致略過一個比較 即p[11]與p[1]的比較被略過！直接比較了p[11]與p[0]！
是否可以略過這個比較？！
答案是肯定的.
根據(jù)邏輯推理 如果p[11]與p[4]不等 而p[4] = p[1]那么p[11]與p[1]一定不等 所以可以略過
這樣說似乎很牽強 我們再回想一下NEXT數(shù)組的意義 即當(dāng)我們比較到i位時不等 應(yīng)該由哪一位重新開始比較 而實際上 這個過程相當(dāng)于在 7-11的這個串中查找0-3！所以根據(jù)NEXT數(shù)組的意義 我們也可以知道 這里并不會導(dǎo)致錯誤 由于被略去的比較一定不需比較 因此 J始終可以得到正確的未修正的NEXT值！
?3。
KMP算法的局限性 由于KMP算法完全由模式串來考慮滑動 可能忽略一些很好的滑動機會
如當(dāng)目標(biāo)串某位不同于模式串時 若此目標(biāo)串中的字符從未在模式串中出現(xiàn) 那么就可以直接滑過去所有的 這時候 目標(biāo)串也起了???確定滑動距離 的作用．這其實就是ＢＭ算法．有興趣的同學(xué)可以參考下列連接
http://www.cnpaf.net/Forum/htm_data/5/0507/1832.html1977年,Robert Boyer和L.Moore發(fā)表了一種新的精確字符串匹配算法,這種算法在邏輯上相對于現(xiàn)有的算法有了很大的超越.它對要搜索的字符串實施逆序字符比較,而且有一種找到了不匹配就不需要對整個字符串進行搜索的方法.這種算法還有最初在PDP-10匯編器上實現(xiàn)的奇跡.
好了 到這里了吧 呵呵 我休息下 最近暈糊涂了