注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

老和山小和尚

敬天爱人

 
 
 

日志

 
 
 
 

一个AC自动机的实现(C语言,BSD许可证)  

2011-05-31 19:12:36|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是前几天工作中碰到的一个查找字串的问题。

以C语言为例,一般我们在查找字符串中的子串时,最简单的是strstr函数。当子串数很少的时候,这个函数还是很简单有效的。但是在实际情况里,我们需要查找很多的子串,如果遍历每个子串都要扫描整个字符串,那复杂度就大了。

假设我们的字符串的长度为n,而所有的字串长度之和为m,那么我们的简单复杂匹配时间复杂度O(nm),这是很显而易见的。

那怎么来进行优化呢?用AC自动机,它其实是KMP算法的多子串的扩展形式!AC自动机的原理是将所有的匹配子串编译成一个状态机,然后将输入的字符串逐字进行状态跳转,如果跳到匹配状态就认为是匹配了。其原理的详细描述可以看[2]。根据[1]的计算,它的时间复杂度只有O(2n),当然它的空间复杂度会有一定的增加,一般与字符串的长度成正比,大约是O(km),k是一定的常量,一般也就几百K的内存。所以与几十倍的时间复杂度节省来说,是非常有益的。

如果你想对AC自动机有比较深入的了解,建议看[1]这篇论文,我的代码基本上就是按照这篇论文的伪代码描述实现的。


[1] Margaret J. Corasick (June 1975). "Efficient string matching: An aid to bibliographic search". Communications of the ACM 18 (6): 333–340. doi:10.1145/360825.360855
  评论这张
 
阅读(2489)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017