【题解】AC自动机泛做

几道AC自动机简单题qwq

以上是原标题。现在整理一遍发现除了第一道题都不太会了,所以题都挺好的QAQ

所以是不是间接证明了「好题」=「由于自己太菜而想不出来的题」啊,听上去好悲伤

$1$ [TJOI2013]单词

小张最近在忙毕设,所以一直在读论文。

一篇论文是由许多单词组成。但小张发现一个单词会在论文中出现很多次,他想知道每个单词分别在论文中出现了多少次。

发现怎么做都可以啦。当时自己似乎是记录了一下关键点(endpos)和每个点的经过次数,然后反向topsort就dp完了。

多攒攒经验,万一哪天就可以一眼秒了呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline void Insert(char *s, int ID){
rr int rt = 0, c ;
for (rr int k = 0 ; s[k] ; ++ k){
c = s[k] - 'a' ;
if (!Trie[rt][c])
Trie[rt][c] = ++ tot ;
rt = Trie[rt][c], ++ res[rt] ;
}
cnt[ID] = rt ;
}
void BFS(){
for (i = 0 ; i < 26 ; ++ i)
if(Trie[0][i]) q.push(Trie[0][i]) ;
while (!q.empty()){
int now = q.front() ; T[++ n] = now ; q.pop() ;
for (i = 0 ; i < 26 ; ++ i)
if (!v(now))
Trie[now][i] = Trie[fail[now]][i] ;
else
fail[v(now)] = Trie[fail[now]][i], q.push(v(now)) ;
}
for (i = n ; i >= 0 ; -- i) res[fail[T[i]]] += res[T[i]] ;
}

$2$ [USACO15FEB]Censoring(Gold)

给出一个长串和一堆小串。每次从长串中找出最靠右的小串,删掉之后拼起来,继续删。求删到最后的串。

$\rm |S|\leq 10^6$

第一眼不会做,我是弟弟QAQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Insert(char *In){
int rt = 0, L = strlen(In) ;
for (int i = 0 ; i < L ; ++ i){
int now = In[i] - 'a' ;
if (!Trie[rt][now])
Trie[rt][now] = ++ cnt ;
rt = Trie[rt][now] ;// 1
}
Id[rt] = L ;
}
void Solve(){
int rt = 0 ;
for (int i = 1 ; i <= Ls ; ++ i){
int now = S[i] - 'a' ;
rt = Trie[rt][now], R[i] = rt, stk[++ top] = i ;
if (Id[rt]) top -= Id[rt], rt = top ? R[stk[top]] : 0 ;
}
}

发现似乎正解出奇的简洁…

然后发现原来「删除一个串再拼起来」这东西就直接顺着扫一遍弹栈就完了…

这题似乎挺考察基本功的吧…像我这种基本功不行的老年选手又被无情吊锤了QAQ

$3$ [NOI2011]阿狸的打字机

有一个打字机,支持三种操作:

  • 字符串末尾加一个小写字母
  • 字符串末尾删一个字符
  • 输出这个字符串

经过不超过 $n$ 次操作后有 $m$ 组询问:$(x,y)$,表示询问第 $x$ 次输出第字符串在第 $y$ 次输出第字符串里出现几次

$1\leq n,m \leq 10^5$

本来没做过这道题,但是一篇文章写两道题总觉得有点不爽,于是决定加一道。

于是就发现自己进了个天坑……本来觉得这题应该挺简单的说(通过题目名称猜的(((

根据 ACAM 的性质,发现所有包含某个串 $\rm S$ 的集合 $O$ 就是 $\rm endpos(S)$ 在 $fail$ 树上的子树。所以每次可以看做查询 $\rm endpos(S_\mathit{x})$ 的 $fail$ 树子树中有多少个单词也在 $\rm S_\it{y}$ 里面。发现「也在 $\rm S_\it{y}$ 里面」这东西可以通过「$\rm endpos(S\mathit{_y})$ 在 Trie 上到根的路径」来表示,于是就直接拿个树状数组维护 $dfs$ 序就可以了。

然后以下是写这个题踩的坑:

  • AC自动机由于求 fail 的时候要路径压缩,所以如果压完直接去 dfs 这个 Trie 的话会错,所以要事先复制一份(因为显然不路径压缩复杂度不对)。
  • 不要忘了AC自动机有 0 号节点,所以 dfn 可能会比编号大 1,加上即可。
  • 这题读入十分鬼畜,导致不能一个一个插入。发现删除就是跳 father ,加入就是走 root,所以也是考察了AC自动机的状态简并性吧。

唉,我太菜了。中间由于思考不足导致走了一堆弯路。且一开始由于 TLE 还觉得是线段树太慢了又写了个 BIT…233

不管不管,这么难写的东西一定要代码全篇贴qwq!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define low(x) (x & -x)

#define to(k) E[k].to
#define next(k) E[k].next
#define pint pair<int, int>

const int N = 200010 ;
const int M = 400010 ;
const int Sigma = 26 ;
const int SZ = 1000010 ;

using namespace std ;

struct Edge{
int to ;
int next ;
}E[M] ;
int m ;
int Id ;
int cnt ;
char S[N] ;
char T[N] ;
int ans[N] ;
int sz[SZ] ;
int _bit[N] ;
int dfn[SZ] ;
int dep[SZ] ;
int head[SZ] ;
int t[N * 3] ;
int tag[N * 3] ;
bool vis[SZ] ;
vector <pint> qs[N] ;

struct ACAM{
int L, rt ;
int fa[SZ] ;
int id[SZ] ;
int sz, tot ;
int _ed[SZ] ;
int _ED[SZ] ;
int fail[SZ] ;
queue <int> q ;
int tr[SZ][Sigma] ;
int trans[SZ][Sigma] ;
/*void Insert(char *S, int len){
L = len, rt = 0, ++ tot ;
//cout << " ** " << len << endl ;
for (int i = 1 ; i <= L ; ++ i){
//cout << S[i] ;
int o = S[i] - 'a' ;
if (!trans[rt][o])
trans[rt][o] = ++ sz ;
rt = trans[rt][o] ;
}
_ed[rt] = tot ; _ED[tot] = rt ; //puts("") ;
}*/
void Workfail(){
for (int i = 0 ; i < Sigma ; ++ i)
if (trans[0][i]) q.push(trans[0][i]) ;
for (int i = 0 ; i <= sz ; ++ i)
for (int j = 0 ; j < Sigma ; ++ j)
tr[i][j] = trans[i][j] ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
for (int i = 0 ; i < Sigma ; ++ i)
if (!tr[x][i]) tr[x][i] = tr[fail[x]][i] ;
else fail[tr[x][i]] = tr[fail[x]][i], q.push(tr[x][i]) ;
}
}
}A ;

void add(int u, int v){
to(++ cnt) = v,
next(cnt) = head[u], head[u] = cnt ;
}
void dfs(int x){
//cout << x << endl ;
dfn[x] = ++ Id ; sz[x] = 1 ;
for (int k = head[x] ; k ; k = next(k)){
dep[to(k)] = dep[x] + 1 ;
dfs(to(k)), sz[x] += sz[to(k)] ;
}
}
/*
void down(int x, int l, int r){
if (tag[x]){
int lc = x << 1 ;
int rc = x << 1 | 1 ;
int mid = (l + r) >> 1 ;
tag[lc] += tag[x] ;
tag[rc] += tag[x] ;
t[rc] += tag[x] * (r - mid) ;
t[lc] += tag[x] * (mid - l + 1) ;
tag[x] = 0 ;
}
}
void update(int rt, int l, int r, int ul, int ur, int v){
if (ul <= l && r <= ur){
t[rt] += v * (r - l + 1) ;
tag[rt] += v ; return void() ;
}
int mid = (l + r) >> 1 ; down(rt, l, r) ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, v) ;
if (mid < ur) update(rt << 1 | 1, mid + 1, r, ul, ur, v) ;
t[rt] = t[rt << 1] + t[rt << 1 | 1] ;
}*//*
void update(int rt, int l, int r, int p, int v){
int mid = (l + r) >> 1 ;
if (l == r)
return t[rt] += v, void() ;
if (p <= mid)
update(rt << 1, l, mid, p, v) ;
else update(rt << 1 | 1, mid + 1, r, p, v) ;
t[rt] = t[rt << 1] + t[rt << 1 | 1] ;
}
int query(int rt, int l, int r, int ql, int qr){
int mid = (l + r) >> 1, ret = 0 ;
if (ql <= l && r <= qr) return t[rt] ;
if (ql <= mid) ret += query(rt << 1, l, mid, ql, qr) ;
if (qr > mid) ret += query(rt << 1 | 1, mid + 1, r, ql, qr) ;
return ret ;
}*/
void mdf(int p, int v){
for ( ; p <= A.sz ; p += low(p)) _bit[p] += v ;
}
int ask(int p){
int res = 0 ;
if (!p) return 0 ;
for ( ; p ; p -= low(p))
res += _bit[p] ;
return res ;
}
void do_do(int x){
//cout << x << endl ;
if (vis[x]) return ; vis[x] = 1 ;
//cout << t[1] << endl ;
mdf(dfn[x], 1) ;
if (A._ed[x]){
int n, k = A._ed[x] ;
for (auto i : qs[k]){
n = A._ED[i.first] ;
ans[i.second] = ask(dfn[n] + sz[n] - 1) ;
ans[i.second] -= ask(dfn[n] - 1) ;
}
}
for (int i = 0 ; i < Sigma ; ++ i)
if (A.trans[x][i]) do_do(A.trans[x][i]) ;
mdf(dfn[x], -1) ;
}
int main(){
int x = 0, y, rt ;
scanf("%s", S + 1) ;
y = strlen(S + 1) ; A.sz = 1 ;
/*for (int i = 1 ; i <= y ; ++ i){
if (S[i] == 'B') x -- ;
else if (S[i] == 'P') A.Insert(T, x) ;
else T[++ x] = S[i] ;
}*/
rt = 0 ;
for (int i = 1 ; i <= y ; ++ i){
if (S[i] == 'B') rt = A.fa[rt] ;
else if (S[i] == 'P')
A._ed[rt] = ++ A.tot, A._ED[A.tot] = rt ;
else {
int o = S[i] - 'a' ;
if (!A.trans[rt][o]) A.trans[rt][o] = ++ A.sz ;
A.fa[A.trans[rt][o]] = rt, rt = A.trans[rt][o] ;
}
}
//cout << A.sz << endl ;
/*for (int i = 1 ; i <= A.sz ; ++ i, puts(""))
for (int j = 0 ; j <= 2 ; ++ j)
cout << A.trans[i][j] << " " ;*/
A.Workfail() ;
/* for (int i = 1 ; i <= A.sz ; ++ i, puts(""))
for (int j = 0 ; j <= 2 ; ++ j)
cout << A.trans[i][j] << " " ;*/
// cout << A.tot << endl ;
for (int i = 1 ; i <= A.sz ; ++ i)
add(A.fail[i], i) ;
// cout << 233 << endl ;
dfs(0) ; cin >> m ;
//for (int i = 0 ; i <= 3 ; ++ i) cout << dep[i] << endl ;
//cout << A.fail[9] << endl ;

//for (int i = 1 ; i <= A.tot ; ++ i) cout << A._ED[i] << " " ; puts("") ;
//for (int i = 1 ; i <= A.sz ; ++ i) cout << A.fail[i] << " " ; puts("") ;
/*for (int i = 1 ; i <= A.sz ; ++ i) cout << sz[i] << " " ; puts("") ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d", &x, &y) ;
x = A._ed[x], y = A._ed[y] ;
//cout << x << " " << y << endl ;
if (dfn[y] >= dfn[x] && dfn[y] <= dfn[x] + sz[x] - 1)
printf("%d\n", dep[y] - dep[x] + 1) ; else puts("0") ;
}
*/
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d", &x, &y),
qs[y].push_back(make_pair(x, i)) ;
do_do(0) ;
for (int i = 1 ; i <= m ; ++ i)
printf("%d\n", ans[i]) ; return 0 ;
}