没有合适的资源?快使用搜索试试~ 我知道了~
PHP版的AC多模式匹配算法
共2个文件
rar:2个
5星 · 超过95%的资源 需积分: 34 124 下载量 162 浏览量
2011-11-15
14:32:40
上传
评论
收藏 23KB RAR 举报
温馨提示
AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字的总长度成正比。 算法思想:用多模式串建立一个确定性的树形有限状态机,以主串作为该有限状态机的输入,使状态机进行状态的转换,当到达某些特定的状态时,说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段。在预处理阶段根据待匹配的模式串组生成有限状态机;搜索查找阶段状态机根据输入的文本串进行状态跳转,当到达某一状态时,该状态有匹配的模式串,则匹配成功。AC 状态机包括goto、fail 和output 3 个函数。 实现步骤:1. 构造字典树;2. 搜索路径的确定(即构造失败指针);3. 模式匹配过程。
资源推荐
资源详情
资源评论
收起资源包目录
ac.php.rar (2个子文件)
ac.php
php.ac.demo.rar 16KB
php.ac.src.rar 6KB
共 2 条
- 1
yangzht2008
- 粉丝: 16
- 资源: 36
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页