這幾天唸 algorithm 剛好念到幾個經典的 algorithm，其中之一就是 O(m+n) 的 KMP algorithm，突然想到 BBS 應該要大量使用這類 O(m+n) 的 algorithm 才對。因為掃一次 pattern 求出 fail function 後 (當然，為了速度要存到 array) 就可以不斷的重複使用。
在 string matching (nist.gov) 有列出不少都是 O(m+n) 的演算法。(當然，O(m*n) 的暴力法一定也會列的啦)
以 M3 (Maple3) 為例，在 ‘~’ 的串接功能，以及 ‘/’ 的中文看板板名搜尋 都應該以 KMP 改寫。於是這幾天就把 KKcity 的 str_str() 換了不少下來，在看板搜尋的部分果然馬上就有感覺。(因為全 KKcity 的看板實在太多了)
應該把 str_str_kmp() 以及 str_str_kmp_fail() 丟出來，接下來 itoc 就會處理了 :p
DK 老大有沒有考慮用 Boyer-Moore 方法呢？
根據實驗與理論的分析，KMP 方法在一般情況下，並不見得會比傳統的寫
法快多少，不過我們事實上還有更好寫而且平均會比 KMP 快的方法存在。這個方
法由 Boyer 與 Moore 兩人差不多與 KMP 方法同時發現，這個題目主要就是在探
討 Boyer-Moore 方法。
還有一篇
boyer-moore不錯，我測試過KMP與Boyer-Moore這兩種pattern match
的方式，實驗結果兩個速度差不多，有時候KMP還輸。我那時候是在
網路封包(都是真實的流量)裡搜尋一些關鍵字用到的，一開始程式不是
我寫的，他用的是boyer-moore，我想試試用KMP會不會比較快，結果發
現差不多就沒換了^^
請問有沒有作approximate string match的algorithm及方法,即是找(l,d)的patterns.給長度l的pattern p,在文件text中找msimatch為k的pattern p1,p2…..像
ATCGGT
| | | |
ATAGTT
ALLOW 2 MISMATCH