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.cppblog.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