CF710F String Set Queries AC自动机+二进制分组
题意：输入n表示操作数，有3种操作。设计一个字符串集合，
1 x 在集合中插入字符串x
2 x 在集合中删除字符串x(保证删除之前x存在)
3 x 询问当前集合中字符串在x中出现次数(计算重复)
强制在线，\sum x_{i} <= 3e5
多字符串匹配，AC自动机，但AC自动机不支持在线添加与删除字符串，所以使用二进制分组，并且创建两组AC自动机。自动机组A用来存放已经添加的字符串，B用来存放已经删除的字符串，A-B就是答案。
二进制分组，即共创建logn组自动机，编号依次为0,1,2··· 每次在0号自动机插入一个字符串，若0号自动机本来就存在，那么就把0号和1号合并，0号自动机此时已销毁，若1号存在，则继续合并···，可以想到i号自动机是由2^i个字符串构建成的，所以只需要nlogn个自动机就可收纳n个字符串，且同一时刻每个字符串最多存在于一个自动机中。每个字符串最多会被合并logn次，每次插入完成后，就build一下，每个字符串最多被build也是logn次。然后询问时，把母串在每个自动机上都跑一遍，也是logn次，最终平均时间复杂度为O(logn)。
代码实现
这里面最难实现的就是合并两个自动机这部分，因为AC自动机是在Trie树上建立起来的，但并不完全是Trie树，每个结点的某个孩子结点可能是实际存在的，即存在字符串经过其孩子结点，但也可能是该孩子结点不存在，而为了匹配加速该孩子结点也会有值，指向一个存在的结点，也就是说AC自动机的Trie树中包含两类结点：一个是在插入字符串时建立的实结点，一个是在AC自动机的build操作中建立的虚结点，用来加速匹配。合并两个自动机时是不考虑虚结点的，所以在插入字符串时要对Trie树中的结点进行虚实标记，便于合并时使用。
新开发的AC自动机的性质：当使用母串扫描AC自动机时，扫描到某个结点，在fail树中从该结点一直到根结点的路径中，终结点的个数就是自动机中字符串的出现次数，这个次数仅仅是该结点的贡献，所有扫描到的结点的贡献加起来就是所有模板串在母串中的出现次数
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
// AC自动机包装成一个结构体 Trie为Trie树，fail表示fail失配指针，cnt表示结点使用个数，end表示有多少个字符串终结于此结点
struct AC_auto {
int Trie[maxn][27], fail[maxn], cnt, val[maxn], end[maxn]; //val表示某个结点的权值，即母串扫描自动机过程中扫描到该结点，对答案所贡献的权值
// val[i]的值等于fail树中从该结点到根节点的路径上end之和
bool mk[maxn][27]; // mk对应于trie树，表示某结点的某个孩子结点是否为真结点
void insert(char *s, int len) {
int root = 0;
for (int i=1; i<=len; i++) {
if (!mk[root][s[i]-'a'+1]) {
Trie[root][s[i]-'a'+1] = ++cnt;
mk[root][s[i]-'a'+1] = true;
}
root = Trie[root][s[i]-'a'+1];
}
end[root] += 1;
return;
}
void build() {
queue<int> q;
for (int i=0; i<=cnt; i++) val[i] = end[i];
for (int i=1; i<27; i++) {
fail[Trie[0][i]] = 0;
if (mk[0][i])
q.push(Trie[0][i]);
}
while (!q.empty()) {
int tmp = q.front(); q.pop();
val[tmp] += val[fail[tmp]];
for (int i=1; i<27; i++) {
if (mk[tmp][i]) {
fail[Trie[tmp][i]] = Trie[fail[tmp]][i];
q.push(Trie[tmp][i]);
}else Trie[tmp][i] = Trie[fail[tmp]][i];
}
}
return;
}
int query(char *s, int len) {
int ans = 0, root = 0;
for (int i=1; i<=len; i++) {
root = Trie[root][s[i]-'a'+1];
ans += val[root];
}
return ans;
}
// AC自动机销毁，把每个实结点的孩子结点指向的值都赋0，每个实结点的各个属性(fail, end, val)都赋0即可
void destory() {
for (int i=0; i<=cnt; i++){
for (int j=1; j<27; j++)
Trie[i][j] = 0, mk[i][j] = false;
fail[i] = 0;
val[i] = 0;
end[i] = 0;
}
cnt = 0;
return;
}
};
struct zyh{
struct AC_auto ACAM[19];
bool vis[20]; // vis[i]=true表示i号自动机存在
void insert(char *s, int len) {
ACAM[0].insert(s, len);
if (!vis[0]) {
ACAM[0].build();
vis[0] = true;
return;
}
int i=0;
for ( ; ; i++) {
if (!vis[i+1]) break;
merge(ACAM[i], ACAM[i+1]);
vis[i] = false;
ACAM[i].destory();
}
merge(ACAM[i], ACAM[i+1]);
ACAM[i].destory();
ACAM[i+1].build();
vis[i] = false, vis[i+1] = true;
return;
}
int query(char *s, int len) {
int ans = 0;
for (int i=0; i<19; i++) if (vis[i])
ans += ACAM[i].query(s, len);
return ans;
}
// 合并两组自动机，把x加到y上，x是不变的
void merge(const struct AC_auto &x, struct AC_auto &y) {
dfs(x, y, 0, 0);
return;
}
void dfs(const struct AC_auto &x, struct AC_auto &y, int a, int b) {
for (int i=1; i<27; i++) if (x.mk[a][i]){
if (!y.mk[b][i]) {
y.Trie[b][i] = ++y.cnt;
y.mk[b][i] = true;
}
y.end[y.Trie[b][i]] += x.end[x.Trie[a][i]];
dfs(x, y, x.Trie[a][i], y.Trie[b][i]);
}
return;
}
}A, B;
int m, t, len;
char s[300005];
int main () {
scanf ("%d", &m);
while (m--) {
scanf ("%d %s", &t, s+1);
len = strlen(s+1);
if (t==1) A.insert(s, len);
else if (t==2) B.insert(s, len);
else {
printf ("%d\n", A.query(s, len) - B.query(s, len));
//cout << A.query(s, len) - B.query(s, len) << endl;
fflush(stdout);
}
}
return 0;
}使用fflush(stdout)语句可以强制把缓存区的内容输出，而不是把所有输入都读完之后才开始输出，这样就会达到强制在线的目的。cout语句在执行完成后会自动检查一次缓冲区，使用cout就不需要使用fflush(stdout)了
0 条评论