- 博客(1)
- 资源 (38)
- 收藏
- 关注
RSS订阅原创 博客地址更改
欢迎大家来到我的CSDN博客空间，先送上本人最诚挚的祝福我的所有文章均放在其它博客上，大家有时间可以去看看，地址如下：http://yangzht2008.blogcn.comhttp://yangzht2008.blog.sohu.com/http://blog.sina.com.cn/yangzht2008
2008-01-30 16:34:00
349
PHP版的AC多模式匹配算法
AC多模式匹配算法
特点：应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点：一是扫描文本时完全不需要回溯，二是时间复杂度为O(n)与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比。
算法思想：用多模式串建立一个确定性的树形有限状态机，以主串作为该有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段。在预处理阶段根据待匹配的模式串组生成有限状态机；搜索查找阶段状态机根据输入的文本串进行状态跳转，当到达某一状态时，该状态有匹配的模式串，则匹配成功。AC 状态机包括goto、fail 和output 3 个函数。
实现步骤：1. 构造字典树；2. 搜索路径的确定(即构造失败指针)；3. 模式匹配过程。
2011-11-15
java版的AC多模式匹配算法
AC多模式匹配算法
特点：应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点：一是扫描文本时完全不需要回溯，二是时间复杂度为O(n)与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比。
算法思想：用多模式串建立一个确定性的树形有限状态机，以主串作为该有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段。在预处理阶段根据待匹配的模式串组生成有限状态机；搜索查找阶段状态机根据输入的文本串进行状态跳转，当到达某一状态时，该状态有匹配的模式串，则匹配成功。AC 状态机包括goto、fail 和output 3 个函数。
实现步骤：1. 构造字典树；2. 搜索路径的确定(即构造失败指针)；3. 模式匹配过程。
2011-11-15
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人