前言
一道比较基础的ACAM题（我也是因为这个题才学了AC自动机）。这边建议没学过AC自动机的先去学一下，我太菜了，没有现成的博客提供给大家 : ( 悲
校内模拟赛也考到了这个题，不过自己人挺善良的给了不少部分分，我当时还很菜（虽然现在也是），就糊了一个KMP骗了50pts~ 不过CF上好像卡的挺死的，就不能这么瞎搞了（怕
简要分析
看到多模式匹配便显然想到了AC自动机，这题只不过就是比正常的AC自动机板子多了添加和删除操作。观察数据范围可得，我们能增加的复杂度最多不能超过 \(\log\) 级别。
我们知道，AC自动机的所有fail边的反向边可构成一棵树（fail树是一颗外向树），证明也很好理解：因为在所有的fail正向边中，所有的点的出度 \(\le 1\) ，所以fail反向边就是入度 \(\le 1\) 。
并且对于fail树来说，以 \(0\) 号节点为根的每一棵子树的字母集大小只有 \(1\) 。如果实在理解不了，就自己多举几个例子手模一下就知道了。
对于添加和删除，我们肯定不能真的添加删除，最先想到的肯定是打标记，对于不会打标记的建议先做一下P3796 【模板】AC 自动机（加强版）。
想明白一个问题，当一个字符串出现的时候，那么它的后缀一定出现。那么fail树的作用就出现了，想想在建立fail数组的时候是从某个字符串的结尾指向其后缀，那么fail树就是从后缀指向某个字符串的结尾，（我太菜了，需要手模一下）就会发现这东西其实是个区间修改。那么我们设一个数组 \(c\) ，令 \(c[i]\) 表示以 \(i\) 为后缀的模式串在母串出现的次数，维护的话就先差分一下再用树状数组单点修改即可。正确性显然。
题说完了，就奉上我（自认为）美丽的代码吧~
#include <bits/stdc++.h>
using namespace std;
const int maxn(1e6 + 3), maxn2(1e5 + 3);
int n, len, m, opt, a;
char str[maxn];
bool vis[maxn];
namespace AC_AUTOMATON {
int trie[maxn][26], cnt, ed[maxn], fail[maxn], rnk[maxn2];
int head[maxn], nxt[maxn], ver[maxn], tot;
queue<int> q;
int in[maxn], out[maxn], num;
class AC_automaton {
public:
inline void add(int x, int y) {
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
inline void insert(char* s, int k) {
int p(0);
len = strlen(s);
for (int i = 0; i < len; ++i) {
if (!trie[p][s[i] - 97]) trie[p][s[i] - 97] = ++cnt;
p = trie[p][s[i] - 97];
}
++ed[p];
rnk[k] = p;
}
void getFail() {
fail[0] = 0;
for (int i = 0; i < 26; ++i) {
if (trie[0][i]) {
q.push(trie[0][i]);
fail[trie[0][i]] = 0;
add(0, trie[0][i]);
}
}
while (q.size()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; ++i) {
if (trie[u][i]) {
q.push(trie[u][i]);
fail[trie[u][i]] = trie[fail[u]][i];
add(fail[trie[u][i]], trie[u][i]);
}
else trie[u][i] = trie[fail[u]][i];
}
}
}
void dfs(int x) {
in[x] = ++num;
for (int i = head[x]; ~i; i = nxt[i]) {
dfs(ver[i]);
}
out[x] = num;
}
} AC;
}
using namespace AC_AUTOMATON;
namespace BINARY_INDEXED_TREE {
int c[maxn];
class Binary_Indexed_Tree {
public:
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int k) {
for (; x <= cnt + 1; x += lowbit(x)) { c[x] += k; }
}
inline int ask(int x) {
int res(0);
for (; x; x -= lowbit(x)) { res += c[x]; }
return res;
}
int query(char* s) {
int res(0), p(0);
len = strlen(s);
for (int i = 1; i < len; ++i) {
p = trie[p][s[i] - 97];
res += ask(in[p]);
}
return res;
}
} BIT;
}
using namespace BINARY_INDEXED_TREE;
int main() {
memset(head, 0xff, sizeof(head));
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", str);
AC.insert(str, i);
}
AC.getFail();
AC.dfs(0);
for (int i = 1; i <= n; ++i) {
BIT.add(in[rnk[i]], 1);
BIT.add(out[rnk[i]] + 1, -1);
}
for (int i = 1; i <= m; ++i) {
scanf("%s", str);
len = strlen(str);
a = 0;
for (int i = 1; i < len; ++i) {
if (str[0] == '+' || str[0] == '-') a = (a << 1) + (a << 3) + (str[i] & 15);
}
if (str[0] == '?') {
printf("%d\n", BIT.query(str));
} else if (str[0] == '+') {
if (vis[a] == true) {
vis[a] = false;
BIT.add(in[rnk[a]], 1);
BIT.add(out[rnk[a]] + 1, -1);
}
} else {
if (vis[a] == false) {
vis[a] = true;
BIT.add(in[rnk[a]], -1);
BIT.add(out[rnk[a]] + 1, 1);
}
}
}
}