【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'的按...
HDU2296 Ring（AC自动机+DP）
题目是给几个带有价值的单词。而一个字符串的价值是 各单词在它里面出现次数*单词价值 的和，问长度不超过n的最大价值的字符串是什么？依然是入门的AC自动机+DP题。。不一样的是这题要输出具体方案，加个字符数组记录每个状态最优情况的字符串即可。另外题目字典序是先考虑长度再考虑每一位单词；特别要注意，有一...
BZOJ3881[Coci2015]Divljak——AC自动机+树状数组+LCA+dfs序+树链的并
题目描述Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。接下来会发生q个操作，操作有两种形式：“1 P”，Bob往自己的集合里添加了一个字符串P。“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的...
P3796 【模板】AC自动机（加强版）
P3796 【模板】AC自动机（加强版）https://www.luogu.org/problemnew/show/P3796题目描述有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。输入输出格式输入格式：输入含多...
[模板][P3808]AC自动机(简单版)
Description:求n个模式串中有几个在文本串中出现Solution：模板，详见代码：#include<bits/stdc++.h>using namespace std;const int mxn=1e7+5;char str[mxn],p[80];queue<int &g...
(转)两种高效过滤敏感词算法--DFA算法和AC自动机算法
原文：https://blog.csdn.net/u013421629/article/details/83178970一道bat面试题：快速替换10亿条标题中的5万个敏感词，有哪些解决思路？有十亿个标题，存在一个文件中，一行一个标题。有5万个敏感词，存在另一个文件。写一个程序过滤掉所有标题中的所有...
hdu_2457_DNA repair(AC自动机+DP)
题目连接：hdu_2457_DNA repair题意：给你N个字符串，最后再给你一个要匹配的串，问你最少修改多少次，使得这个串不出现之前给的N的字符串题解：刚学AC自动机，切这题还真不知道怎么来DP，然后看了一下题解，需要在失败指针那里做文章，这里我们要将trie的每一个节点当作一个状态，然后设dp...
HDU2243 考研路茫茫——单词情结（AC自动机+矩阵快速幂）
与POJ2778一样。这题是求长度不超过n且包含至少一个词根的单词总数。长度不超过n的单词总数记为Sn，长度不超过n不包含词根的单词总数记为Tn。答案就是，Sn-Tn。Sn=26+262+263+...+26nTn=A+A2+A3+...+An （A为AC自动机构造出来的矩阵）可以构造矩阵用快速幂求...
【无聊放个模板系列】BZOJ 3172 (AC自动机)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #incl...
【CF710F】String Set Queries（二进制分组，AC自动机）
【CF710F】String Set Queries（二进制分组，AC自动机）题面洛谷CF翻译：你有一个字符集合\(D\)，初始为空，有三种操作：往\(D\)中加入一个串；从\(D\)中删除一个串；给定一个串\(S\)，询问\(D\)中的串在\(S\)中总共出现了多少次。题解询问显然就是将\(S\)...
HDU 2222（AC自动机模板题)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2222题目大意：多个模式串。问匹配串中含有多少个模式串。注意模式串有重复，所以要累计重复结果。解题思路：AC自动机模板题。一开始使用LRJ的坑爹静态模板，不支持重复的模式串。在做AC自动机+DP的时候，...
HDU 2243 考研路茫茫——单词情结（AC自动机+矩阵）
考研路茫茫——单词情结Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2687 Accepted Submission(s): 744...
算法笔记--字典树（trie 树）&& ac自动机 && 可持久化trie
字典树简介：字典树，又称单词查找树，Trie树，是一种树形结构，是哈希树的变种。优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。性质：根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所...
ZOJ 4114 Detect the Virus（AC自动机）
Detect the VirusTime Limit: 2 Seconds Memory Limit: 65536 KBOne day, Nobita found that his computer is extremely slow. After several hours' work,...
bzoj 1444 AC自动机 + 矩阵乘法 | 高斯消元
恶补了一下AC自动机，花了一天时间终于全部搞明白了。思路：将每个人的串加入AC自动机，在AC自动机生成的状态图上建边，注意单词末尾的节点只能转移到自己概率为1，然后将矩阵自乘几十次后误差就很小了， 或者可以高斯消元搞出精确解。#include<bits/stdc++.h>#define ...
AC 自动机 模板
简单版#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>#include <cmath>#in...
BZOJ 3940--[Usaco2015 Feb]Censoring（AC自动机）
3940: [Usaco2015 Feb]CensoringTime Limit: 10 Sec Memory Limit: 128 MBSubmit: 723 Solved: 360[Submit][Status][Discuss]DescriptionFarmer John has purc...
HDU 2457 DNA repair（AC自动机+DP）题解
题意：给你几个模式串，问你主串最少改几个字符能够使主串不包含模式串思路：从昨天中午开始研究，研究到现在终于看懂了。既然是多模匹配，我们是要用到AC自动机的。我们把主串放到AC自动机上跑，并保证不出现模式串，这里对AC自动机的创建有所改动，我们需要修改不存在但是符合要求的节点，如果某节点的某一子节点不...
Codeforces 710F - String Set Queries（AC 自动机）
题面传送门题意：强制在线的 AC 自动机。\(n,\sum|s|\leq 3\times 10^5\)如果不是强制在线那此题就是道 sb 题，加了强制在线就不那么 sb 了。这里介绍两种做法：根号分治考虑到 KMP 擅长处理单个字符串匹配的情况，但对于多模式串的情况复杂度就不那么优秀了。而 AC 自...