支持字符串的插入和删除。。。SAM也干不了这个事
所以可以用cdq分治+AC自动机O(nlogn)解决
但是本题强制在线~~~
我们还有一个工具，叫做二进制分组！
所以，每组建立一个AC自动机，合并的时候，AC自动机合并。最后再build失配指针
随机删除？虽然不是栈序删除了，但是，统计数量具有贡献独立性，再对删除串建立一个AC自动机集群即可！
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=3e5+;
int m;
int ch[N][];
int vis[N][];
int fail[N],num[N],tot[N];
int rt[N],sz[N];
int cnt,totid;
struct AC{
int sta[N],top;
int merge(int x,int y){
// cout<<"merge "<<x<<" "<<y<<endl;
if(!x||!y) return x+y;
for(reg i=;i<;++i) ch[x][i]=merge(ch[x][i],ch[y][i]);
num[x]+=num[y];
return x;
}
void build(int id){
queue<int>q;
for(reg i=;i<;++i){
if(ch[rt[id]][i]) fail[vis[rt[id]][i]=ch[rt[id]][i]]=rt[id],q.push(vis[rt[id]][i]);
else vis[rt[id]][i]=rt[id];
}
while(!q.empty()){
int x=q.front();q.pop();
tot[x]=num[x]+tot[fail[x]];
for(reg i=;i<;++i){
if(ch[x][i]){
fail[vis[x][i]=ch[x][i]]=vis[fail[x]][i];
q.push(vis[x][i]);
}else{
vis[x][i]=vis[fail[x]][i];
}
}
}
}
int query(char *s){
int len=strlen(s+);
int ret=;
for(reg i=;i<=top;++i){
int id=sta[i];
int now=rt[id];
for(reg i=;i<=len;++i){
now=vis[now][s[i]-'a'];
ret+=tot[now];
}
}
return ret;
}
void ins(char *s){
int id=++totid;
int len=strlen(s+);
if(!rt[id]) rt[id]=++cnt;
int now=rt[id];
for(reg i=;i<=len;++i){
int x=s[i]-'a';
ch[now][x]=++cnt;
now=ch[now][x];
}
++num[now];
//dfs(rt[id]);
// cout<<rt[id]<<" "<<cnt<<endl;
sz[id]=;
// cout<<" after ins "<<id<<endl;
while(top&&sz[sta[top]]==sz[id]) rt[id]=merge(rt[id],rt[sta[top]]),sz[id]+=sz[sta[top]],--top;
// cout<<" after merge "<<endl;
build(id);
sta[++top]=id; }
}f,d;
char s[N];
int main(){
rd(m);
int op;
for(reg i=;i<=m;++i){
rd(op);scanf("%s",s+);
if(op==)f.ins(s);
else if(op==)d.ins(s);
else {
printf("%d\n",f.query(s)-d.query(s));
}
fflush(stdout);
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/24 15:19:38
*/
二进制分组，对于许多插入删除根本不虚，反正暴力重构删除，O(nlogn)
（当然如果贡献不独立，还是cdq或者线段树分治吧，，）