string

         glibc里的strstr函數(shù)用的是brute-force(naive)算法，它與其它算法的區(qū)別是strstr不對pattern(needle)進行預(yù)處理，所以用起來很方便。理論復(fù)雜度O (mn), 實際上，平均復(fù)雜度為O(n), 大部分情況下高度優(yōu)化的算法性能要優(yōu)于基于自動機的匹配算法，關(guān)于串匹配算法可參考http://www-igm.univ-mlv.fr/~lecroq/string/。 glibc中使用了（1）Stephen R. van den Berg的實現(xiàn)，在他的基礎(chǔ)上，（2）Tor Myklebust http://sources.redhat.com/ml/libc-alpha/2006-07/msg00028.html給出了更復(fù)雜的實現(xiàn)，當(dāng)然也更高效。
       BF有一個重要性質(zhì)是事先不用知道串的長度，而基于跳躍的算法是需要用字符串長度來判斷結(jié)束位置的。如何快速的確定字符串結(jié)束位置，可參考http://www.shnenglu.com/ant/archive/2007/10/12/32886.html，寫的很仔細(xì)。
      將兩種思想結(jié)合起來，可以做出更快的strstr（3）。約定（1） 為strstr(Berg); (2) 為strstr(Tor)，（3）為lstrstr(mine)，（4）為glibc中的strstr，簡單測試了一下：
      從長度為2k的文本中查找長度為1、2、9的模式串，結(jié)果如下
            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