KMP和AC自动机
KMP： 给定模式串$A[1~n]$和匹配串$B[1~m]$，求出$A$在$B$中出现的位置。 这就是经典的字符串匹配问题了，也许你会说$Hash$也可以线性解决，为什么还要学$KMP$？ 因为$KMP$的作用并不仅仅是解决字符串匹配问题，$KMP$过程中得到的$Next$数组还可以在一些问题中发挥...
从KMP到AC自动机
不想写题。不如写写算法总结？ KMP 介（che）绍（dan） 以前都不知道\(KMP\)为什么叫\(KMP\)，现在才明白：该算法是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，以其名字首字母命名。\(KMP\)可以在\(O(n+m)\)的时间复杂度内解决判定一...
AC自动机练习
目录 AC自动机 HDU 2896 指针写法（爆内存，MLE） 数组写法（AC） AC自动机 HDU 2896 指针写法（爆内存，MLE） #include <iostream>#include <cstring>#include <...
AC自动机及KMP练习
好久都没敲过KMP和AC自动机了。以前只会敲个kuangbin牌板子套题。现在重新写了自己的板子加深了印象。并且刷了一些题来增加自己的理解。 KMP网上教程很多，但我的建议还是先看AC自动机（Trie图）的构造后再去理解。板子的话大家大同小异。 而AC自动机的构造则是推荐王贇的《Trie图的构建、活...
AC自动机练习
多模板串匹配一般有两种方法 暴力kmp, 适用于模板串少的情形 直接trie上暴力, 适用于模板串比较短的情形, 并且可以动态插入合并 建立AC自动机, 复杂度是严格线性的, 但不能动态插入 const int N = 1e6+10;int n, tot, T, ok;int val[N],...
AC自动机和KMP
AC自动机存储一个字符串的集合,把他叫做T.用i(s)表示字符串s的代表节点. 用s(i)表示节点i的代表字符串. 构建需要的时间是 $O(nc)$ 的,n为字符个数,c为字符集的大小. AC自动机的性质. 1.从根到一个节点的路径是T中某些字串的前缀. (trie 基本性质) 2.从一个节点到...
关于AC自动机和DP的联系
首先是描述个大概。不说一些特殊的DP 或者借用矩阵来状态转移 （这些本质都是一样的）。只讲AC自动机和DP的关系（个人理解）。AC自动机 又可以叫做状态机。我一开始的认为。AC 自动机提供了一些节点的信息。以及那些节点之间的关系。（节点也就是我们创建的 Trie图的节点。往往我们会有一维这个信息）。...
【bzoj3530】[Sdoi2014]数数 AC自动机+数位dp
题目描述我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。给定N和S，计算不大于N的幸运数个数。输入输入的第一行包含整数N。接下来一行一个整数M，表示S中元...
【bzoj2938】[Poi2000]病毒 AC自动机
题目描述二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如果{011, 11, 00000}为病毒代码段，那么一个...
【BZOJ2938】[Poi2000]病毒 AC自动机+DFS
【BZOJ2938】[Poi2000]病毒Description二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如...
BZOJ 2938: [Poi2000]病毒 [AC自动机 拓扑排序]
2938: [Poi2000]病毒题意：判断是否存在无限长的不含模式串的字符串。只有01.建出套路DP的转移图，判断有环就行了练习一下拓扑排序#include <iostream>#include <cstdio>#include <cstring>#includ...
LightOJ 1427 -Repository（ac自动机）
题意：求每个模式串在母串中出现的次数#include <map>#include <set>#include <list>#include <cmath>#include <queue>#include <stack>#incl...
BZOJ3172 [Tjoi2013]单词 【AC自动机】
3172: [Tjoi2013]单词Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 4293 Solved: 2083[Submit][Status][Discuss]Description某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论...
bzoj千题计划315：bzoj3172: [Tjoi2013]单词（AC自动机）
https://www.lydsy.com/JudgeOnline/problem.php?id=3172构建AC自动机在fail树上，点i的子树大小 表示trie树上根节点到i构成的单词 是 多少个(子)串的子串#include<queue>#include<cstdio>...
hdu 4117 -- GRE Words (AC自动机+线段树)
题目链接problemRecently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words...
hdu 2222 Keywords Search（AC自动机）
/* 啥也不说了，直接套模板。。。 */ 1 #include<iostream> #include<map> #include<string> #include<cstring> #include<queue> #defi...
【POJ3691】DNA repair（AC自动机，DP）
题意：生物课上我们学到，DNA序列中只有A, C, T和G四种片段。经科学发现，DNA序列中，包含某些片段会产生不好的基因，如片段”ATC”是不好片段，则”AGATCC”, “CATCAA”, “ATCATC”都是不好的DNA序列，这些不好片段我们可以称为病毒片段。现在已知m个病毒片段， 然后给定一...
[BJOI2019]奥术神杖（分数规划+AC自动机+DP）
题解：很显然可以对权值取对数，然后把几何平均值转为算术平均值，然后很显然是分数规划。先对每个模式串建立AC自动机，每个节点w[i],sz[i]分别表示以其为前缀的字符串，然后再二分最优解k，然后w[i]-=k*sz[i]，然后枚举T，在AC自动机上DP一遍，求最大值是否大于0即可。#include&...
【Luogu3041】视频游戏的连击（AC自动机，动态规划）
题面链接题解首先构建出AC自动机然后在AC自动机上面跑DP转移很显然从Trie树的节点跳到他的儿子节点但是要注意一个问题，在计算的时候，每一个节点加入后能够造成的贡献要加上他的子串的贡献至于DP：设f[i][j]表示已经使用了i个字母当前在Trie树的第j个节点上面能够产生的最大贡献很显然，转移到他...
【AC自动机】【字符串】【字典树】AC自动机 学习笔记
blog:www.wjyyy.top AC自动机是一种毒瘤的方便的多模式串匹配算法。基于字典树，用到了类似KMP的思维。 AC自动机与KMP不同的是，AC自动机可以同时匹配多个模式串，而复杂度不会达到太高。如果用KMP多次匹配字符串，复杂度就是\(O(k(n+m))\)。 我们知道...