自动机专题

hdu 3065 AC自动机匹配串编号以及出现次数

题意：仍旧是天朝语题。 Input 第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。

POJ 1625 自动机

给出包含n个可见字符的字符集，以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串，求长为m且不包含上述p个字符串的字符串有多少个。 g++提交 int mat[108][108] ;int matn ;int N ;map<char ,int> to ;//ACconst int maxm = 108 ;const int kin

zoj 3228 ac自动机

给出一个字符串和若干个单词，问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现，1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

正规式与有限自动机例题

答案：D 知识点：正规式正规集举例 ab 字符串ab构成的集合 {ab} a|b 字符串a,b构成的集合 {a,b} a^* 由0或者多个a构成的字符串集合 {空,a,aa,aaa,aaaa····} (a|b)^* 所有字符a和b构成的串的集合 {空,a,b,ab,aab,aba,aaab····} a(a|b)^* 以a为首字符的a,b字符串的集

AC自动机 - 多模式串的匹配运用 --- HDU 3065

病毒侵袭持续中 Problem's Link：http://acm.hdu.edu.cn/showproblem.php?pid=3065 Mean: 略 analyse: AC自动机的运用. 这一题需要将模式串都存储下来，还有就是base的取值一定要弄清楚，由于这题的模式串都是大写字母所以我们可以通过剪枝来加速。 Time complexity：o(n)+o(m

AC自动机 - 多模式串的匹配运用 --- HDU 2896

病毒侵袭 Problem's Link：http://acm.hdu.edu.cn/showproblem.php?pid=2896 Mean: 略 analyse: AC自动机的运用，多模式串匹配。就是有几个细节要注意，在这些细节上卡了半天了。 1)输出的网站编号和最终的病毒网站数不是一样的； 2)next指针要设128,不然会爆栈； 3)同理，char转换为i

[置顶]论如何优雅的处理回文串 - 回文自动机详解

写在前面最近无意中看到了这个数据结构，顺便也就学习了一下。而且发现网上关于这个算法的描述有很多地方是错的，在这里做了一些更正。处理字符串的算法很多： KMP,E-KMP,AC自动机,后缀三兄弟:后缀树、后缀数组、后缀自动机,Trie树、Trie图,符串hash... 但以上数据结构在处理回文串上还是稍有欠缺，用这些来处理回文显得太小题大做。于是有了Manacher算

[置顶]AC自动机-算法详解

What's Aho-Corasick automaton? 　　一种多模式串匹配算法，该算法在1975年产生于贝尔实验室，是著名的多模式匹配算法之一。　　简单的说，KMP用来在一篇文章中匹配一个模式串；但如果有多个模式串，需要在一篇文章中把出现过的模式串都匹配出来，就需要Aho-Corasick automaton算法了。 My Understanding About Aho-Coras

【HDU】3065 病毒侵袭持续中 AC自动机

病毒侵袭持续中 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5766 Accepted Submission(s): 2028 Problem Description 小t非常感谢大家帮忙解决了他的上一个

【HDU】2896 病毒侵袭 AC自动机

病毒侵袭 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10087 Accepted Submission(s): 2612 Problem Description 当太阳的光辉逐渐被月亮遮蔽，世界失去了光

【codeforces】163E. e-Government AC自动机+树状数组

传送门：【codeforces】163E. e-Government 题目分析：感觉到现在再做类似题目已经感觉很水了= =。。。这题也就是构建了fail指针树以后树状数组维护就好了。10^6个字母的意思就是说我们可以随便搞。。。代码如下： #include <cstdio>#include <cstring>#include <algorithm>using n

【HDU】4117 GRE Words AC自动机+线段树优化DP

传送门：【HDU】4117 GRE Words 题目分析：水不了啊狸的打字机就来水这题了= =。。。首先建立ac自动机，然后用fail指针的反向关系建边，构造fail指针树。fail指针树中每个结点u表示的串都是其子节点v的后缀（同时该后缀是所有串中最长的）。对fail指针树dfs一次得到时间戳，当要求以串i结尾的最大价值，首先我们需要知道以串i的子串j结尾的最大价值val。因为在树中

【HDU】5343 MZL's Circle Zhou【后缀自动机】

传送门：【HDU】5343 MZL’s Circle Zhou 对于a串可能和b串重复的部分，我们总能找到一个位置，使得a串达到最长，即a串的后继为空，所以我们只要预处理以字符x为开头的b串的个数即可。 my code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#defin

【HDU】5566 Clarke and room【树链剖分+AC自动机】

题目链接：Clarke and room #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define ls ( o << 1 )#define lson ls , l , m#define rs ( o << 1 | 1 )#define rson rs , m + 1 , r#define rt

AC自动机白书模板

模板： struct ACauto{ int ch[maxn][26]; int sz; int f[maxn],last[maxn],val[maxn],cnt[maxn]; void init() { sz=1; memset(ch[0],0,sizeof ch[0]); memset(cnt,0,sizeof cnt); } int idx(char c) { return c-'

经验笔记：状态机与下推自动机的理解与应用场景

经验笔记：状态机与下推自动机的理解与应用场景引言在软件开发和计算机科学领域，状态机和下推自动机是两个重要的概念，它们帮助我们理解和设计各种类型的系统。本文将简要介绍这两种模型，并详细探讨它们的应用场景。状态机概述状态机是一种数学模型，它通过一组状态、事件、转移条件以及动作来描述一个系统的动态行为。状态机的核心在于它的状态转换机制，即在给定条件满足时，系统如何从一个状态转移到另一个状

hdu3065--病毒侵袭持续中(AC自动机入门3)

病毒侵袭持续中 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7185 Accepted Submission(s): 2531 Problem Description 小t非常感谢大家帮忙解决了他的上一个问

hdu2896--病毒侵袭(AC自动机入门2)

病毒侵袭 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 12771 Accepted Submission(s): 3290 Problem Description 当太阳的光辉逐渐被月亮遮蔽，世界失去了光明

【字符串新武器】后缀自动机

发链：http://neroysq.blogcn.com/articles/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%88%9D%E6%8E%A2.html http://blog.sina.com.cn/s/blog_7812e98601012cim.html 详细构造见上述链接，此处介绍性质与理解后缀自动机具有两大性质，

Codeforces Round #327 (Div. 1) E. Birthday【AC自动机+网络流】

先用AC自动机处理子串的问题建立AC自动机，在上面标记出这个位置含有的串（ num[v] num[v]）以及维护fail指针含有的串（ last[v] last[v]）。这是简单的处理，和沈阳站的B题简直异曲同工。然后形成了一个DAG图，再用floyd算法将维护出整个DAG图。用网络流Dinic处理最大独立集的问题，胡伯涛的论文有提及二分图的最大独立集做法。将DAG拆点转化为二分图

BZOJ 3530 数数【AC自动机+数位dp】

[Sdoi2014]数数简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法状态，一个是前缀零的情况。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostr

$AC自动机-2（AhoCorasickDoubleArrayTrie）$