CF710 F String Set Queries

CF710 F String Set Queries

CF710 F String Set Queries

题意

维护一个字符串集合,支持三种操作:

  1. 加字符串
  2. 删字符串
  3. 查询集合中的所有字符串在给出的模板串中出现的次数

本题强制在线,应该在每次输入后调用fflush(stdout),你只有在输出上一个询问的答案后才能读入下一组询问。

思路

开两套AC自动机,一个插入一个删除,最后插入减去删除

题解代码

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
#include <bits/stdc++.h>
using namespace std;
int gi() //快读
{
int x = 0, w = 1;
char ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-')
ch = getchar();
if (ch == '-')
w = 0, ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return w ? x : -x;
}
const int N = 3e5 + 5;
struct AC
{
int son[26][N], end[N], tr[26][N], fa[N], cnt[N], tot;
int rt[N], sz[N], top;
queue<int> Q;
void getfail(int RT)
{
for (int i = 0; i < 26; ++i)
if (son[i][RT])
fa[tr[i][RT] = son[i][RT]] = RT, Q.push(tr[i][RT]);
else
tr[i][RT] = RT;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 0; i < 26; ++i)
if (son[i][u])
{
tr[i][u] = son[i][u], fa[tr[i][u]] = tr[i][fa[u]];
Q.push(tr[i][u]);
}
else
tr[i][u] = tr[i][fa[u]];
cnt[u] = end[u] + cnt[fa[u]];
}
}
int merge(int x, int y)
{
if (!x || !y)
return x | y;
end[x] += end[y];
for (int i = 0; i < 26; ++i)
son[i][x] = merge(son[i][x], son[i][y]);
return x;
}
void insert(char *s, int n)
{
rt[++top] = ++tot;
sz[top] = 1;
int x = rt[top];
for (int i = 1; i <= n; ++i)
{
if (!son[s[i] - 'a'][x])
son[s[i] - 'a'][x] = ++tot;
x = son[s[i] - 'a'][x];
}
end[x] = 1;
while (sz[top] == sz[top - 1])
{
--top;
rt[top] = merge(rt[top], rt[top + 1]);
sz[top] += sz[top + 1];
}
getfail(rt[top]);
}
int query(char *s, int n)
{
int res = 0;
for (int i = 1; i <= top; ++i)
for (int j = 1, x = rt[i]; j <= n; ++j)
x = tr[s[j] - 'a'][x], res += cnt[x];
return res;
}
} T1, T2;
char s[N];
int main()
{
int m = gi();
while (m--)
{
int op = gi();
scanf("%s", s + 1);
int n = strlen(s + 1);
if (op == 1)
T1.insert(s, n);
if (op == 2)
T2.insert(s, n);
if (op == 3)
printf("%d\n", T1.query(s, n) - T2.query(s, n)), fflush(stdout);
}
return 0;
}

重点解析

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
/*
字典树:
https://www.colabug.com/2018/0905/4379063/
AC自动机:
https://www.cnblogs.com/hyfhaha/p/10802604.html
*/

/*
AC自动机模板自我理解:
*/
void getFail() //建立fail指针
{
for (int i = 0; i < 26; i++) //初始化0的所有儿子都是1
trie[0].son[i] = 1;
q.push(1); //将根压入队列
trie[1].fail = 0; //第一层的fail都指向0
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) //遍历所有儿子
{
int v = trie[u].son[i]; //处理u的i儿子的fail
int Fail = trie[u].fail; //trie[Fail].son[i]就是和v值相同的点
if (!v) //不存在
{
trie[u].son[i] = trie[Fail].son[i];//直接让这一位等于后缀的下一位
continue;
}
trie[v].fail = trie[Fail].son[i]; //第三种情况,直接指就可以了
q.push(v); //存在实节点才压入队列
}
}
}

int query(char *s)
{ //查询
int u = 1, ans = 0, len = strlen(s);
for (int i = 0; i < len; i++)
{
int v = s[i] - 'a';
int k = trie[u].son[v]; //跳Fail
while (k > 1 && trie[k].flag != -1)
{ //经过就不统计了
ans += trie[k].flag, trie[k].flag = -1; //累加上这个位置的模式串个数,标记已经过
k = trie[k].fail; //继续跳Fail
}
u = trie[u].son[v]; //到儿子那,存在性看上面的第二种情况
}
return ans;
}