hannibal_Iecter

ac自动机

bitset(2) BSGS(1) dfs(3) DP(19) ODT(1) splay(1) ST表(2) tarjan(2) 中途相遇法(1) 主席树(4) 二分图(1) 二叉树(1) 分块(1) 分治(3) 回文树(1) 多校(1) 字符串(1) 容斥(2) 平衡树(5) 并查集(1) 快速乘(1) 数学(9) 整体二分(1) 树链剖分(2) 模拟退火(2) 水题(1) 爬山算法(1) 矩阵快速幂(2) 线性基(1) 线段树(10) 编译器(2) 背包(2) 莫队(1) 计算几何(1) 随机数(1) 高精度(1)

/ 注册

全部文章 / ac自动机（共7篇）

HDU-2825[AC自动机+状压dp]

不要被状压吓倒了。。和之前用AC自动机求构造字符串的数量方法类似，但是这个问题要多开一维状态表示包含多少特殊的串。 dp[i][j][k]表示长度为i已经匹配到j的串包含特殊串的状态为k的数量。转移方程是dp[i][u][s|ed[u]] += dp[i-1][j][s](u = j->ch...

2019-04-09

0 420

poj-1625 Censored![ac自动机+dp+高精度]

题目地址先把病毒串丢进ac自动机里面。 dp[i][j]表示长度为i的从trie图的根节点到j满足条件的串的数量。因为答案很大，要用到高精度。注意的是建图的时候，ed[u] |= ed[f[u]]，如果失配指针的位置是病毒的话那么u也不能匹配。 #include<cstdio> ...

2019-04-07

0 421

bzoj-2434阿狸的打字机[AC自动机+fail树+dfs序+树状数组]

前置知识： ac自动机 fail树关键在于fail树的应用：子节点的后缀一定包含父节点。对于x在y中出现了多少次。先假设y至少包含一个x。那么在trie图中从根节点到y的那条链中一定存在某个节点的后缀是x。所以找到这样的节点就能知道包含x的数量。处理：我们可以按照打字的...

2019-04-06

0 415

bzoj-3172单词[fail树]

fail树的性质：子节点是以父节点为后缀的串。对于这道题，我们用num[]维护每个串出现的次数，在insert的时候对每个节点都要加一，表示这个节点已经出现过一次了。最后我们构建fail树，然后把每个子节点的num都加到当前节点上就是这个串总共出现的次数了。 #include<bits/...

2019-04-06

0 397

SPOJ - WPUZZLES[AC自动机]

首先把所有拼图丢到自动机里面。然后从边界位置枚举各种可能的方向。 ac自动机的询问就可以判断一下当前节点是否是结尾然后记录答案。 #include<bits/stdc++.h> using namespace std; const int maxn = 1e3+5; char ma...

2019-04-06

0 360

zoj3441 Searching the String

对于可以覆盖的串，直接上模板。对于不能覆盖的串，可以记录字典树中当前节点在询问串中的上一次询问的位置。然后对于不能覆盖的询问，用当前串的位置减去上一次询问字典树中当前节点的位置和当前深度比较一下就行了。 #include<bits/stdc++.h> using namespace ...

2019-04-06

0 319

【模板】ac自动机

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+5; int n, cnt[200]; char temp[20...

2019-02-03

0 343