menu zcmimi's blog

arrow_back AC自动机

有多种做法

AC自动机暴力

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

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

AC自动机暴力

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

对点名串建立AC自动机

zc
2020-05-17 16:09

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

然后构建AC自动机

利用了fail树的一个性质:

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

zc
2020-05-08 19:19

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2020-02-02 21:51

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

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

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

主席树在线也可以 ```cpp

incl

zc
2020-02-02 17:36

n\le12

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

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

看到这个可以联想

zc
2019-12-21 19:47

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

还是练一下AC自动机吧

解释见代码 ```cpp

include<b

zc
2019-12-21 19:47
1 / 1
Search
search