传送门

DFS序基础

思路:

先建立$Fail$树.并得到$Fail$树的$DFS$序
对于查询可以分析得知:每次查询的答案就是当前指针到根节点的$fail$链上的标记数量.
对于修改可以分析得知:每次修改以后Fail树上一点$u$,只会对子树到$root$的$fail$链的答案产生响.

因此可以将查询和修改 转化成:区间修改和单点查询.
每次修改的时候就相当于修改子树.
每次查询的时候用相当于树状数组维护了树上差分.
单点查询的时候就等价求区间和

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N];
int cnt[N],tr[N][26],q[N],fail[N];
struct Query{
        string s;
        int type,id;
}query[N];
int n,m,tot;
void add(int a,int b)
{
        e[tot]=b,ne[tot]=h[a],h[a]=tot++;
}
int insert(string s)
{
        int p=0;
        for(int i;s[i];i++)
        {
                int u=s[i]-'a';
                if(!tr[p][u])tr[p][u]=++idx;
                p=tr[p][u];
        }
        cnt[p]++;
        return p;//建树 
}
void build()
{
        int hh=0,tt=0;
        for(int i=0;i<26;i++)
         if(tr[0][i])
         {
                 q[tt++]=tr[0][i];
                 add(0,tr[0][i]);
         }

        while(hh!=tt)
        {
                int t=q[hh++];
                for(int i=0;i<26;i++)
                {
                        int u=tr[t][i];
                        if(!u)tr[t][i]=tr[fail[t]][i];
                        else
                        {
                                fail[u]=tr[fail[t]][i];
                                add(fail[u],u);//建fail树 
                                q[tt++]=u;
                        }
                }
        }
}
int dfn[N],R[N],timestamp;
void dfs(int u)
{
        R[u]=timestamp,dfn[u]=timestamp++;
        for(int i=h[u];~i;i=ne[i])
        {
             int j=e[i];
             dfs(j);
             R[u]=R[j];  //更新子树中最大时间戳      
        } 
}
int sum[N];
int lowbit(int x){return x&-x;};
void modify(int x,int c)
{
        for(int i=x;i<=idx;i+=lowbit(i))sum[i]+=c;
}
int cal(int x)
{
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))res+=sum[i];
        return res;
}
int get(string s)
{
        int res=0;
        int u=0;
        for(int i=0;s[i];i++)
        {
                int t=s[i]-'a';
                u=tr[u][t];
                res+=cal(dfn[u]);
        }
        return res;
}
void init()
{
        tot=idx=timestamp=0;
        memset(h,-1,sizeof h);
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(fail,0,sizeof fail);
        memset(dfn,0,sizeof dfn);
        memset(R,0,sizeof R);
        memset(sum,0,sizeof sum);
}
void solve()
{
       cin>>n>>m;
       init();
       for(int i=0;i<n;i++)
       {
            string s;cin>>s;
            insert(s);
       } 
       for(int i=1;i<=m;i++)
       {
               cin>>query[i].type>>query[i].s;
               if(query[i].type==1)
               {
                       query[i].id=insert(query[i].s);
                       cnt[query[i].id]--;
               }
       }
       build();
       dfs(0); 
       for(int i=0;i<idx;i++)
        if(cnt[q[i]])modify(dfn[q[i]],1),modify(R[q[i]]+1,-1);

       for(int i=1;i<=m;i++)
        if(query[i].type==1)cnt[query[i].id]++,modify(dfn[query[i].id],1),modify(R[query[i].id]+1,-1);
        else  cout<<get(query[i].s)<<endl;

       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}