string

string
posts - 27, comments - 177, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

strstr

Posted on 2008-10-27 21:42 djx_zh 阅读(3128) 评论(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://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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理