维护一个集合支持：
$1.$ 添加一个串。
$2.$ 删除一个串。
$3.$ 给出一个串，询问有多少个子串在集合中出现过，多次出现多次计算。
若没有强制在线就直接离线打标记 $\text{AC}$ 自动机即可。
但是这题需要强制在线。
考虑最暴力的算法，即为建立两个 $\text{AC}$ 自动机，将加入的串和删除的串分别丢进去，每次暴力重构，最后直接跑匹配答案相减即可。
显然这种做法的时间复杂度是非常不科学的，思考时间复杂度到底在哪里爆炸了，发现是多次暴力重构的问题。
考虑是否有一种方案能够以较少的暴力重构次数来维护这个问题，那么我们想到了二进制分组。
对于每 $2^k$ 个串维护一个 $\text{AC}$ 自动机，这样即维护了一个 $\text{AC}$ 自动机的栈。
这样最多共有 $\log$ 个 $\text{AC}$ 自动机，插入时如果当前 $\text{AC}$ 自动机中串的个数和前个数相同，那么合并两个自动机。每个字符串只会被合并 $\log$ 次，每次合并时暴力重构即可。
//Dlove‘s template
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define R register
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define sqr(_x) ((_x) * (_x))
#define Cmax(_a, _b) ((_a) < (_b) ? (_a) = (_b), 1 : 0)
#define Cmin(_a, _b) ((_a) > (_b) ? (_a) = (_b), 1 : 0)
#define Max(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define Min(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define Abs(_x) (_x < 0 ? (-(_x)) : (_x))
using namespace std;
namespace Dntcry
{
inline int read()
{
R int a = 0, b = 1; R char c = getchar();
for(; c < ‘0‘ || c > ‘9‘; c = getchar()) (c == ‘-‘) ? b = -1 : 0;
for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) a = (a << 1) + (a << 3) + c - ‘0‘;
return a * b;
}
inline ll lread()
{
R ll a = 0, b = 1; R char c = getchar();
for(; c < ‘0‘ || c > ‘9‘; c = getchar()) (c == ‘-‘) ? b = -1 : 0;
for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) a = (a << 1) + (a << 3) + c - ‘0‘;
return a * b;
}
const int Maxn = 300010;
int m, len;
char S[Maxn];
struct node
{
int key, tim;
node *ch[26], *ac[26], *fail;
}pool[Maxn << 2], *tot = pool, *q[Maxn << 2];
struct ACM
{
node *rt[30];
int cnt, siz[30];
void Insert(R node *root)
{
R node *x = root;
for(R int i = 1; i <= len; i++)
{
R int opt = S[i] - ‘a‘;
if(!x->ch[opt]) x->ch[opt] = ++tot;
x = x->ch[opt];
}
x->key = 1;
}
void Build(R node *root)
{
R int head = 0, tail = 0;
root->tim = 0, root->fail = root;
q[++tail] = root;
for(R int i = 0; i < 26; i++) root->ac[i] = root;
while(head < tail)
{
R node *x = q[++head];
x->tim = x->fail->tim + x->key;
for(R int i = 0; i < 26; i++)
if(x->ch[i])
{
q[++tail] = x->ch[i];
x->ch[i]->fail = x->fail->ac[i];
x->ac[i] = x->ch[i];
}
else x->ac[i] = x->fail->ac[i];
}
}
node *Merge(R node *x, R node *y)
{
if(!x) return y;
if(!y) return x;
x->key += y->key;
for(R int i = 0; i < 26; i++)
x->ch[i] = Merge(x->ch[i], y->ch[i]);
return x;
}
void Make()
{
rt[++cnt] = ++tot;
Insert(rt[cnt]);
siz[cnt] = 1;
while(cnt > 1 && siz[cnt] == siz[cnt - 1])
{
rt[cnt - 1] = Merge(rt[cnt - 1], rt[cnt]);
//puts("merged");
siz[cnt - 1] += siz[cnt];
siz[cnt--] = 0;
}
Build(rt[cnt]);
}
int Query()
{
R int res = 0;
for(R int x = 1; x <= cnt; x++)
{
R node *now = rt[x];
for(R int i = 1; i <= len; i++)
{
now = now->ac[S[i] - ‘a‘];
res += now->tim;
}
}
return res;
}
}In, Out;
int k, last;
int Main()
{
scanf("%d%d", &m, &k);
while(m--)
{
R int opt;
scanf("%d%s", &opt, S + 1);
len = strlen(S + 1);
if(k) for(R int i = 1; i <= len; i++) S[i] = ‘a‘ + (S[i] - ‘a‘ + last) % 26;
switch(opt)
{
case 1: In.Make(); break;
case 2: Out.Make(); break;
case 3: last = In.Query() - Out.Query(); printf("%d\n", last); break;
}
}
return 0;
}
}
int main()
{
return Dntcry :: Main();
}
原文：https://www.cnblogs.com/DntcryBecthlev/p/10448284.html