(Large atural) CF163E e-Government 原题链接
解法
这种题算是比较套路的了，我们看见这种多字符串匹配，会想到AC自动机。
如果不会AC自动机的可以看看 我的博客 ，希望能给您带来帮助。
那么如果我们对于所有字典树节点连边 (i-fail_i)（根节点没有 (fail)，不连边），那么就得到了一棵 Fail树。
那么，如果一号点为根节点，那所有 (fail) 直接或间接指向 (i) 号点的节点，都在 (i) 的子树中。
所以查询字符串 (X) 在字符串 (Y) 中出现几次，等价于建出 Trie 和 Fail树 后，在 Fail树中 以 “(X)的结束节点”（设为 (i)） 为根的子树中有多少个 (Y) 包含的节点。
不理解可以看这解释：比如 (j) 号点是 (Y) 所包含的，是 (Y) 的第 (id) 个节点，那么代表在 (Y) 查询时，(j) 跑 (fail) 可以跑出 (X)，所以 (X) 是 (Y) 中 (1sim id) 这个子串的后缀。
先想想只有询问怎么做：
设询问的字符串为 (T)，则显然有这样一个方法：让 (T) 在 Trie 上跑，经过的点对于的 Fail树节点权值加一。设一个字符串在 Trie 的结尾节点为 (G)，然后我们查询集合 (S) 中每个字符串的 (G) ，对应的 Fail树节点 ，的子树和（可能有点绕）。最后我们再把那些加一的点再减一，复原原来的树。
然而这样时间显然会炸。
但是，给 (T) 的路径赋值，然后查询每个 (G) 的子树权值 等价于 给 (G) 的子树赋值，然后查询 (T) 的路径权值。
所以我们一开始给每个 (G) 的子树加一，询问时 (T) 在 Trie 上跑，每跑到一个节点，就加上这个节点对应的 Fail树 节点的权值。这个操作的复杂度是 (O(|T|)) 的。
这样修改操作也迎刃而解，增加字符串 (A) 就给 (G_A) 子树加一，删除就减一。
最后一个问题：怎么样给一个节点的子树加减？只需要在树的 DFS序 上操作即可。因为一个点的子树在 DFS序 上是连续的，所以我们只用区间加值（给子树加减）、单点询问（ (T) 在 Trie 跑时查询）就行了，显然套分块模板即可。
代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
#define kwei(x) ((x-1)/B+1)
#define kl(x) ((x-1)*B+1)
#define kr(x) (x*B)
using namespace std;
const int n7=1012345;
struct dino{int to,nxt;}e[n7];
int n,T,B,ecnt,fst[n7],a[n7],blo[n7],cnt=1,tre[n7][26],fail[n7];
int ned[n7],head,tail,que[n7],t,L[n7],R[n7];
char cr[n7];bool exi[n7];
int rd(){
int shu=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))shu=(shu<<1)+(shu<<3)+(ch^48),ch=getchar();
return shu;
}
void edge(int sta,int edn){
ecnt++;
e[ecnt]=(dino){edn,fst[sta]};
fst[sta]=ecnt;
}
void insert(int z){
int len=strlen(cr+1),now=1;
rep(i,1,len){
int ch=cr[i]-'a';
if(!tre[now][ch]){
cnt++,tre[now][ch]=cnt;
}
now=tre[now][ch];
}
ned[z]=now;
}
void Gfail(){
head=1,tail=1,que[1]=1;
rep(i,0,25)tre[0][i]=1;
while(head<=tail){
int now=que[head];
rep(i,0,25){
int edn=tre[ fail[now] ][i];
if(tre[now][i]){
fail[ tre[now][i] ]=edn;
edge(edn,tre[now][i]);
tail++,que[tail]=tre[now][i];
}
else tre[now][i]=edn;
}
head++;
}
}
void dfs(int o){
t++,L[o]=t;
mar(o)dfs(v);
R[o]=t;
}
void updat(int l,int r,int val){
if( kwei(l)==kwei(r) ){
rep(i,l,r)a[i]+=val;
return;
}
rep(i,l,kr( kwei(l) ))a[i]+=val;
rep(i,kl( kwei(r) ),r)a[i]+=val;
rep(i,kwei(l)+1,kwei(r)-1)blo[i]+=val;
}
int Tquery(int z){
return a[z]+blo[ kwei(z) ];
}
int query(){
int len=strlen(cr+1),now=1,tot=0;
rep(i,1,len){
now=tre[now][ cr[i]-'a' ];
tot+=Tquery( L[now] );
}
return tot;
}
int main(){
T=rd(),n=rd();
rep(i,1,n)scanf("%s",cr+1),insert(i);
Gfail(),dfs(1);
B=sqrt(cnt*2);//事实证明，块长这样设会玄学地更快，直接卡到最优解1st
rep(i,1,n)exi[ ned[i] ]=1,updat(L[ ned[i] ],R[ ned[i] ],1);
while(T--){
char sys=getchar();
while(sys!='-'&&sys!='+'&&sys!='?')sys=getchar();
if(sys=='+'){
int z=ned[ rd() ];
if(!exi[z])updat(L[z],R[z],1),exi[z]=1;
}
if(sys=='-'){
int z=ned[ rd() ];
if(exi[z])updat(L[z],R[z],-1),exi[z]=0;
}
if(sys=='?'){
scanf("%s",cr+1);
printf("%d
",query());
}
}
return 0;
}