AC自动机的一点理解
2024-09-04 13:46:18
\(fail\)指针:指向最长的在\(tire\)里出现的后缀
比\(tire\)多出来的子边:原来的\(tire\),我们失配后又得返回根结点再次匹配,而加入这些边后只需要花\(strlen(s)\)就能实现所有匹配
跑\(tire\)图:能跑到一个结点,该结点所代表的串能被文本串表示
例题
问题1:多个模式串,一个文本串,有几个模式串出现在文本串内
做法:对于多个模式串建自动机,文本串匹配,匹配到的点及\(fail\)点的代表的串都在文本串中
具体操作+优化:我们对于每个串的末端点\(val_i\)都记录代表几个串(建\(trie\)),在\(trie\)图中不变,然后每次匹配到的点往上爬并累加\(val\)值并标记,
之后再爬的时候到过标记了的点就退出,则保证了时间复杂度
问题2:多个模式串,一个文本串,求每个模式串出现的次数
做法:对于多个模式串建自动机,文本串匹配,匹配到的点及\(fail\)点的代表的串都在文本串中,并让这些串次数都+1
具体操作+优化:第一题我们用标记保证了时间复杂度,可这题需要得求每个串出现的次数,标记一下以后就找不到了怎么办?
先把文本串匹配一下,经过的点记录值,然后用topsort来处理,按相当于键fail树从叶子节点往上传,这样就能得到每个点代表的串出现的次数
最后再比较一下每个串的末节点出现的次数
最新文章
- [LeetCode] Copy List with Random Pointer 拷贝带有随机指针的链表
- Android 轻松实现仿淘宝地区选择
- Being a Good Boy in Spring Festival 尼姆博弈
- Tomcat 部署:工程下 META-INF 目录下的 Context.xml
- Spring实现AOP的4种方式(转)
- 几本关于PHP安全的书
- eclipse 软件的背景颜色、字体设置
- PCIE卡槽还能这样用!
- float 属性详解
- findbugs, checkstyle, pmd的myeclipse7.5+插件安装(转:http://blog.csdn.net/priestmoon/article/details/63941)
- Cent OS 7 安装海峰、极点五笔输入法
- TZOJ 1693 Silver Cow Party(最短路+思维)
- 设计模式 笔记 装饰模式 Decorator
- HDU 4819 Mosaic (二维线段树&;区间最值)题解
- requests bs4 爬取 资讯 图片
- jsp页面,jstl标签中的数据在<;%%>;java中使用
- 自学tensorflow——2.使用tensorflow计算线性回归模型
- 在腾讯云服务器上体验Docker
- Spring AOP 不同配置方式产生的冲突问题
- ASP.NET OAuth 2.0 新手上路