已阅读5页，还剩11页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、字典树(Trie) 前缀树 单词查找树一种数据结构，用于存储多个字符串支持的操作：1.插入新的字符串2.查询一个字符串 cap , cat , catch ca cap , cat , catch capt cap , cat , catch capt：表示该节点是一个单词的结尾 cap , cat , catch captch cap , cat , catch, cater captcher字典树之所以存储（空间）和查找（时间）都相当高效，是因为它最大程度地利用了不同字符串之间的最长公共前缀。AC自动机就是基于字典树而产生的算法AC自动机Accedpted auto machine!Aho
2、-Corasick automationAcfun auto machine!用于处理多模板字符串匹配的自动机模型KMP：线性字符串+失配边AC自动机：Trie+失配边chjc：j的第c个子结点chjc=0 ：该子结点不存在如何理解多维情况下的fail边？heisrsshe he , his , hers , she 1234567890令sj表示从根到j节点路径上的字符所构成的字符串则s fj 是sj的最长后缀f3=2f6=4f8=f9=1其他结点k，fk=0状态转移的过程就是沿着树边和fail边走的过程QuestionHintwhile(j & !chji) j=fjfv=chji复杂度建Trie预处理匹配O(n)其实上述算法并不是完整的AC自动机如果一个文本T中的一个字母是多个模板的结尾？需要一个额外数组last来记录。同时也是提高效率
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 车站装修批荡施工协议
- 防腐施工应急预案合同
- 互联网项目招投标合同注意事项
- 化工行业招待费管理新方法
- 花艺助理劳动合同注意事项
- 供水供电收费管理：发票管理办法
- 食品饮料输送管道施工
- 2025版空置房屋闲置资源盘活利用合作开发合同3篇
- 临时办学场所租赁合同
- 2025版二零二五年度新能源充电桩建设与运营合同3篇
- 编码规则(标准)
- 家政培训行业的发展趋势与前景分析
- 定制酒项目投资分析及可行性报告
- 售后客服年终工作总结汇报
- 教师专业化发展经费保障制度
- 家长会课件：初二家长座谈会课件
- 健康照护师（初级）理论知识考核试题
- 物理九年级全册知识点总结（沪粤版）
- 20567-5纳税筹划-教案及讲稿
- 部编版三年级上册作文评价表
- 2019MATLAB-Simulink电力系统建模与仿真第2版
评论
0/150
提交评论