zcmimi's blog

arrow_backAC自动机共7篇文章

avatar
zc
2020-10-13 19:58:29

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

avatar
zc
2020-05-17 16:09:00
查看原题

点击跳转

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

avatar
zc
2020-05-08 19:19:00
查看原题

点击跳转

首先根据输入的字符串构造trie

然后构建AC自动机

利用了fail树的一个性质:

y节点的fail指针指向x节点,那么 根到x形成的字符串 一定在 根到y形成的字符串 中出现过

那么我们对于每个询问x y,只需要找出根到y上的节点有多少个fail指针直接或间接指向x的,就是答案

构建fail树之后使用dfs序+树状数组统计

avatar
zc
2020-02-02 21:51:00
查看原题

点击跳转

avatar
zc
2020-02-02 17:36:00
查看原题

点击跳转

AC自动机建完fail树之后子树的siz就是里面相同字符串的个数

每个询问可以拆成r的前缀和-l的前缀和

然后离线处理后用树状数组维护就可以了

主席树在线也可以

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

LG 4824 [USACO15FEB]Censoring"的做法hash,kmp什么的因为数据水所以跑不满可以水过去

还是练一下AC自动机吧

解释见代码

1/1
Search
search