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