在校内OJ上A了，没有加强制在线的东西。。不放链接了。

这道题题意是维护一个字符串集合，支持三种操作：

1.加字符串

2.删字符串

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

操作数\(m \le 3*10^5\)，输入字符串总长度\(maxL \le 4*10^6\)

对于查询想到了要用AC自动机。但是还要插入和删除，每次插入一个字符串都得重构fail指针，删除更不可做。

对于删除，我们可以新建一颗代表删除的字符串集合的AC自动机，这样查询只要两个AC自动机的值相减即可。

对于插入，发现没有什么高级数据结构可以高效的维护AC自动机的fail指针，每次合并时暴力重构fail指针都是不可避免的。

这样参考splay启发式合并的思想，每个节点最多被操作\(logn\)次。

我们把字符串集合2进制分组(跟字符串元素的长短没有关系)，每次加入一个字符串就把它加入\(2^0\)那一组，如果\(2^0\)那一组本来就有一个字符串，那么把这两个字符串合并到一个trie里并准备加到\(2^1\)那一组，然后再检查\(2^1\)那一组里是否原来就有\(2^1\)个字符串......加到第一个没有元素的组，再对代表这一组的trie构建fail指针。

类似2进制加法，因为每个字符串至多被加\(logn\)次，查询时查询\(logn\)个AC自动机，所以复杂度\(O(nlogn)\)。

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 4000003;

int in() {

	int k = 0; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar());

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - 48;

	return k;

}

struct AC_Auto {

	int ch[N][26], fail[N], val[N], end[N], root[19], tot, cnt, rt;

	AC_Auto() {

		tot = 0; cnt = 20;

		rt = 20;

	}

	void merge(int rt1, int rt2) {

		end[rt2] |= end[rt1];

		for (int i = 0; i < 26; ++i) {

			if (!ch[rt1][i]) continue;

			if (!ch[rt2][i]) ch[rt2][i] = ch[rt1][i];

			else merge(ch[rt1][i], ch[rt2][i]);

		}

	}

	queue <int> q;

	void build_fail(int r) {

		while (!q.empty()) q.pop();

		q.push(r); fail[r] = val[r] = 0;

		int u, p, v;

		while (!q.empty()) {

			u = q.front(); q.pop();

			for (int i = 0; i < 26; ++i)

				if (ch[u][i]) {

					q.push(v = ch[u][i]);

					p = fail[u];

					while (p && !ch[p][i]) p = fail[p];

					fail[v] = p ? ch[p][i] : r;

					val[v] = val[fail[v]] + end[v];

				}

		}

	}

	void ins(char *s) {

		int len = strlen(s), tmp = rt;

		for (int i = 0; i < len; ++i)

			ch[tmp][s[i] - 'a'] = ++cnt, tmp = cnt;

		end[tmp] = 1;

		for (int i = 0; i < 19; ++i)

			if (!root[i]) {

				root[i] = i + 1;

				memcpy(ch[root[i]], ch[rt], sizeof(ch[rt]));

				memset(ch[rt], 0, sizeof(ch[rt]));

				build_fail(root[i]);

				break;

			} else {

				merge(root[i], rt);

				root[i] = 0;

			}

	}

	int r[N];

	int query(char *s) {

		int len = strlen(s), tmp, ans = 0;

		for(int j = 0; j < len; ++j) r[j] = s[j] - 'a';

		for(int i = 0; i < 19; ++i)

			if (root[i]) {

				tmp = root[i];

				for(int j = 0; j < len; ++j)

					if (ch[tmp][r[j]])

						ans += val[tmp = ch[tmp][r[j]]];

					else {

						while (tmp && !ch[tmp][r[j]]) tmp = fail[tmp];

						if (ch[tmp][r[j]]) {

							tmp = ch[tmp][r[j]];

							ans += val[tmp];

						} else

							tmp = root[i];

					}

			}

		return ans;

	}

} *add, *del;

char s[300003];

int main() {

	add = new AC_Auto;

	del = new AC_Auto;

	int op, T = in();

	while (T--) {

		op = in();

		scanf("%s", s);

		switch (op) {

			case 1: add->ins(s); break;

			case 2: del->ins(s); break;

			case 3: printf("%d\n", add->query(s) - del->query(s));

			break;

		}

	}

	return 0;

}