string

         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://www.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