题目描述
Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。
接下来会发生q个操作，操作有两种形式：
“1 P”，Bob往自己的集合里添加了一个字符串P。
“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的子串）
Bob遇到了困难，需要你的帮助。
题解
多串匹配问题，可以想到用AC自动机维护。
对于这种询问，每个串至多贡献一次的问题。
先是把每个T串在AC自动机上跑一遍，获得了一个点集，那么这些点在fail树上到根的路径上的所有点都会被贡献一次。
相当于这些链的并都被贡献了。
那我们的任务就是求链并。
一种方法是将所有点排一个序，然后对每个点到根的路径上加1，相邻两个点的LCA处-1。
链加不太好写，可以转化成统计子树和的形式，用BIT维护。
代码
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 2000002 using namespace std; typedef long long ll; queue<int>q; int tot,ch[N][26],head[N],f[N],zh[N],topp,n,tr[N],tag[N],size[N],deep[N],fa[N],son[N],top[N],dfn[N],dfnn,tott,fan[N]; char s[N]; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct edge{int n,to;}e[N]; inline void add(int u,int v){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;} inline void get_fail(){ for(int i=0;i<26;++i)if(ch[0][i]){q.push(ch[0][i]),add(0,ch[0][i]);} while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<26;++i){; if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],add(f[ch[u][i]],ch[u][i]),q.push(ch[u][i]); else ch[u][i]=ch[f[u]][i]; } } } inline void upd(int x,int y){while(x<=dfnn)tr[x]+=y,x+=x&-x;} inline int query(int x){int ans=0;while(x)ans+=tr[x],x-=x&-x;return ans;} inline void ins(int id){ int len=strlen(s);int now=0; for(int i=0;i<len;++i){ if(!ch[now][s[i]-'a'])ch[now][s[i]-'a']=++tott; now=ch[now][s[i]-'a']; } tag[id]=now; } void dfs(int u){ size[u]=1;//cout<<u<<" "; for(int i=head[u];i;i=e[i].n){ int v=e[i].to;deep[v]=deep[u]+1;fa[v]=u; dfs(v); size[u]+=size[v]; if(size[v]>size[son[u]]||!son[u])son[u]=v; } } void dfs2(int u){ if(!top[u])top[u]=u;dfn[u]=++dfnn;fan[dfnn]=u; if(son[u])top[son[u]]=top[u],dfs2(son[u]); for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(v!=son[u])dfs2(v); } } int getlca(int u,int v){ while(top[u]!=top[v]){ if(deep[top[u]]<deep[top[v]])swap(u,v); u=fa[top[u]]; } return min(dfn[u],dfn[v]); } int main(){ n=rd(); for(int i=1;i<=n;++i){scanf("%s",s);ins(i);} get_fail(); dfs(0);dfs2(0); int q=rd(); while(q--){ int opt=rd(); if(opt==1){ scanf("%s",s);int len=strlen(s),now=0;topp=0; for(int i=0;i<len;++i){ now=ch[now][s[i]-'a']; zh[++topp]=dfn[now]; } sort(zh+1,zh+topp+1); for(int i=1;i<=topp;++i){ upd(zh[i],1); if(i!=1)upd(getlca(fan[zh[i-1]],fan[zh[i]]),-1); } } else{ int x=tag[rd()]; printf("%d ",query(dfn[x]+size[x]-1)-query(dfn[x]-1)); } } return 0; }