Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
【模板】AC自动机(加强版)【AC自动机fail树上求最多出现次数】
题目链接 P3796 给出N个模式串 然后我们用一个文本串去进行匹配 这样的做法 就是AC自动机了 于是乎 我们可以先将N个模式串丢进去 然后建立fail树 然后先对所有的节点求出最大串在文本串中出现的次数 然后利用dfs跑fail树的办法
AC自动机
Keywords Search 【HDU - 2222】【AC自动机模板】
题目链接 学习AC自动机的第一道题 可能跟广大学友是一样的 让我知道了什么是AC自动机 具体讲一下吧 它就是用来求多串匹配的 而KMP只是求单串匹配的 相当于是在KMP上做了优化 之后 就是怎么构造AC自动机了 知道它就是在一棵字典树上做文
AC自动机
数据结构
Wireless Password 【HDU - 2825】【AC自动机+状压DP】
题目链接 好题一道 推了一会 然后计算了一下时间复杂度 差不多最坏情况是25 100 1024 26 66560000然后看了下 嗯 能搞 有搞头哈哈哈 然后写了一下 首先 WA了 发现竟然是最大极限哪儿写错了 我的个天呐 A 我们看到最多
DP动态规划
数据结构
AC自动机
DP
病毒侵袭持续中 【HDU - 3065】【AC自动机】
题目链接 就是求的是每个病毒出现的次数 可以重叠 嗯 最后别忘了释放内存 不然听说会MLE 但是我比较规矩 不会遇到这种现象的 MLE了一次 就记得要释放内存了 是一道AC自动机的模板题 include
AC自动机
数据结构
Searching the String 【ZOJ - 3228】【AC自动机+last跳板优化时间】
题目链接 这次要求的有两个 分别是0 1 代表着的是可以重叠 以及不可以重叠的遍历到该单词的次数 可以重叠的很容易 遇到的时候 就直接加上就是了 但是不可以重叠的时候呢 就需要看到该单词它和上一次的状态出现的距离差了 看一下是否比这个单词长
数据结构
AC自动机
病毒侵袭 【HDU - 2896】【AC自动机】
题目链接 开动态字典树外带内存释放 卡过C 再多一丢丢都要MLE的那种哦 还是很爽的 这道题与这一道题不同就不同在不能去减 能用的就都要用上 然后就直接输出就是了 美滋滋 一开始还是写错了些 忘记给used 数组初始化 然后有些地方没有写上
数据结构
AC自动机
Clannad【2018四川省赛】【AC自动机 + DP】
题目链接 第十届四川省赛C题 挺好的一道题 就是要做一个last优化 每次的last要返回到之前的有值节点 也就是单词的尾的对应节点 然后就不会超时了 呜呜呜 之前一直超时 以为是初始化的memset 问题 以前被卡过memset 然后发现
数据结构
AC自动机
DP动态规划
[NOI2011]阿狸的打字机【AC自动机fail树+树状数组】
题目链接 P2414 题目给出N个字符串 我们现在想知道的是第x个字符串在第y个字符串中出现的次数是多少次 求每个字符在其余字符中出现次数 想到从AC自动机上走 其实可以看作是求它的后缀的前缀中有多少个是满足的 换言之 我们可以去fail树
AC自动机
DNA repair 【HDU - 2457】【AC自动机+DP思路】
题目链接 开始肝这道题的时候也是冒了十足的勇气 呜呜呜 当时一直没发现 我有个地方写成了 s i A 怎么能这样用啊 毕竟只有A C G T的说 呜呜呜 QAQ 然后讲一下 这道题的AC自动机的想法 还有DP的思路 我DP超菜 能过也是超神
DP动态规划
数据结构
AC自动机