hduoj-----(2896)病毒侵袭(ac自动机)
病毒侵袭Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11909 Accepted Submission(s): 3088Probl...
BZOJ 3998: [TJOI2015]弦论 [后缀自动机 DP]
3998: [TJOI2015]弦论Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 2152 Solved: 716[Submit][Status][Discuss]Description对于一个给定长度为N的字符串，求它的第K小子串是什么。Inpu...
hdu_3341_Lost's revenge(AC自动机+状态hashDP)
题目链接：hdu_3341_Lost's revenge题意：有n个模式串，一个标准串，现在让标准串重组，使得包含最多的模式串，可重叠，问重组后最多包含多少模式串题解：显然是AC自动机上的状态压缩DP，不过如果直接开404*500的数组显示开不下，所以这样要将状态hash一下，然后再DP，因为这个字...
DP(记忆化搜索) + AC自动机 LA 4126 Password Suspects
题目传送门题意：训练指南P250分析：DFS记忆化搜索，范围或者说是图是已知的字串构成的自动机图，那么用 | (1 << i)表示包含第i个字串，如果长度为len，且st == (1 << m) - 1则是可能的。打印与之前相似。#include <bits/stdc+...
HDU-4057 Rescue the Rabbit（AC自动机+DP）
Rescue the RabbitTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2036 Accepted Submission...
【BZOJ3530】数数（AC自动机，动态规划）
【BZOJ3530】数数（AC自动机，动态规划）题面BZOJ题解很套路的\(AC\)自动机+\(DP\)首先，如果长度小于\(N\)就不存在任何限制直接大力\(DP\)然后强制限制不能走到带有标记的点上面如果长度恰好为\(N\)的长度那么，要考虑是否恰好卡在范围里面于是\(DP\)状态多记一维表示是...
[TJOI2015]弦论(后缀自动机)
/*一道在树上乱搞的题目建立出parent树来， 然后就能搞出每个节点往后能扩展出几个串， 至于位置不同算同一个的话就强制让right集合大小为1即可然后在树上类比权值线段树找第k大26分统计一下即可 */#include<cstdio>#include<algorithm>...
【元胞自动机】基于matlab元胞自动机模拟SEIR传播模型【含Matlab源码 2156期】
一、元胞自动机简介1 元胞自动机发展历程 最初的元胞自动机是由冯 · 诺依曼在 1950 年代为模拟生物 细胞的自我复制而提出的. 但是并未受到学术界重视.1970 年, 剑桥大学的约翰 · 何顿 · 康威设计了一个电脑游戏 “生命游戏” 后, 元胞自动机才吸引了科学家们的注意.1983 年 S.W...
AC自动机技巧
AC自动机技巧可以用树上的一些算法来进行优化对于要求支持插入和删除字符串的题目，可以通过建两个AC自动机，查询的时候作差来实现。当给出的查询串是一个含有空格的文本时，可以用特殊字符（比如'z'+1）来替换掉空格。AC自动机技巧的更多相关文章小结：ac自动机复杂度: 查找O(n),维护O(n) 概要:...
HDU 2222 AC自动机 裸题
题意：问母串中出现多少个模式串注意ac自动机的节点总数#include <stdio.h>#include <string.h>#include <queue>using namespace std;inline int Max(int a,int b){retu...
hdu 2222 Keywords Search ac自动机入门
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2222题意:有N(N <= 10000)个长度不超过50的模式串和一个长度不超过1e6的文本串。其中模式串可以重复。问有多少文本串在模式串中出现过。(对于相同的模式串次数仍然累加)思路:ac自动机裸...
BZOJ3676 APIO2014回文串（manacher+后缀自动机）
由于本质不同的回文子串数量是O(n)的，考虑在对于每个回文子串在第一次找到它时对其暴力统计。可以发现manacher时若右端点移动则找到了一个新回文串。注意这样会漏掉串长为1的情况，特判一下。现在问题变为统计一个子串的出现次数。可以用SA，二分乱搞一下即可。这里使用SAM。以parent树上表示该子...
洛谷P4770 [NOI2018]你的名字 [后缀自动机，线段树合并]
传送门思路按照套路，直接上后缀自动机。部分分：\(l=1,r=|S|\)首先把\(S\)和\(T\)的后缀自动机都建出来。考虑枚举\(T\)中的右端点\(r\)，查询以\(r\)结尾的串最长可以往左延伸多长，使得它仍然是\(S\)的子串。记该长度为\(lim_r\)。\(lim_r\)可以在\(SA...
hdu----(3065)病毒侵袭持续中(AC自动机)
病毒侵袭持续中Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6721 Accepted Submission(s): 2372Pro...
AC自动机算法小结
AC自动机,可惜不能自动AC转载：飘过的小牛 OIer55242简介Aho-Corasick automation该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。要搞懂AC自动机，先得有字...
【POJ3691】 DNA repair （AC自动机+DP）
DNA repairTime Limit: 2000MSMemory Limit: 65536KB64bit IO Format: %I64d & %I64uDescriptionBiologists finally invent techniques of repairing DNA th...
【BZOJ2434-[Noi2011]】阿狸的打字机（AC自动机（fail树）+离线+树状数组）
Description阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l 按一下印有'B'的按...
详解Python 实现元胞自动机中的生命游戏(Game of life)
本篇文章主要介绍了详解Python 实现元胞自动机中的生命游戏(Game of life)，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
UVALive-4670 Dominating Patterns（AC自动机）
题目大意：找出出现次数最多的模式串。题目分析：AC自动机裸题。代码如下：# include<iostream># include<cstdio># include<map># include<queue># include<cstring>...
HDU2296 Ring（AC自动机+DP）
题目是给几个带有价值的单词。而一个字符串的价值是 各单词在它里面出现次数*单词价值 的和，问长度不超过n的最大价值的字符串是什么？依然是入门的AC自动机+DP题。。不一样的是这题要输出具体方案，加个字符数组记录每个状态最优情况的字符串即可。另外题目字典序是先考虑长度再考虑每一位单词；特别要注意，有一...