Posted on 2008-10-27 21:42
djx_zh 閱讀(3156)
評論(0) 編輯 收藏 引用
glibc里的strstr函數用的是brute-force(naive)算法，它與其它算法的區別是strstr不對pattern(needle)進行預處理，所以用起來很方便。理論復雜度O (mn), 實際上，平均復雜度為O(n), 大部分情況下高度優化的算法性能要優于基于自動機的匹配算法，關于串匹配算法可參考
http://www-igm.univ-mlv.fr/~lecroq/string/。 glibc中使用了（1）Stephen R. van den Berg的實現，在他的基礎上，（2）
Tor Myklebust http://sources.redhat.com/ml/libc-alpha/2006-07/msg00028.html給出了更復雜的實現，當然也更高效。
BF有一個重要性質是事先不用知道串的長度，而基于跳躍的算法是需要用字符串長度來判斷結束位置的。如何快速的確定字符串結束位置，可參考
http://m.shnenglu.com/ant/archive/2007/10/12/32886.html，寫的很仔細。
將兩種思想結合起來，可以做出更快的strstr（3）。約定（1） 為strstr(Berg); (2) 為strstr(Tor)，（3）為lstrstr(mine)，（4）為glibc中的strstr，簡單測試了一下：
從長度為2k的文本中查找長度為1、2、9的模式串，結果如下
1 2 9
（1）0.000006 0.000006 0.000012
（2）0.000007 0.000004 0.000008
（3）0.000002 0.000002 0.000005
（4）0.000005 0.000005 0.000011
download strstr
downlaod