CF710F String Set Queries

颓颓颓颓颓颓颓颓颓+复习AC自动机=啥也不会了

传送门

首先要用AC自动机跑匹配。

然后就是删除非常容易，只要再开一个AC自动机记录被删除得到串，然后在两个AC自动机中跑两次得到两个答案减一下就好了。

设总串长是S，操作数是m，之后就有很多的做法了：

1. 根号分治：把长度大于$\sqrt{S}$的串用hash匹配，其他的串插到一个trie里，之后hash暴力匹配长的串，而trie的深度不超过$\sqrt{S}$，再暴力枚举后缀匹配trie就做完了。
2. 根号重构：每$\sqrt{m}$个串开一个AC自动机，攒够$\sqrt{m}$个就新加进来一个，直接做。
3. AC自动机+二进制分组，考虑当前串的个数是n，对于n在二进制下的第i位数字$s_i$，就维护一个有$s_i\times 2^i$个串的trie，加入的时候从第0位开始做二进制加法，给n加一。进位的时候把当前位上的trie拿出来和上一位上来的trie合并，之后加到下一位，直到有一位是0，就停在这里，把一路合并上来的trie建成AC自动机。 查询的时候每一位跑一遍，由于每个串最多被重构$log\ n$次所以复杂度是对的。

为了复习AC自动机，我写了第三种做法，发现AC自动机全忘了。。。

由于要把trie树合并，所以以往直接在ch数组上补trie图的方法行不通了，不过可以另开一个ch2数组专门用于补trie图，因为zz翻译把串长从3e5错写成4e6，所以空间开的下。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct trie{
    int ch[26],fail,cnt,ch2[26],sum;
}t[300001];
char ch[300001];
int root[2][300001],tot,num[2],n,q;
int head,tail,team[300001],dg[2][300001];
inline void build_trie(int x,int z){
    root[z][x]=++tot; int u=tot;
    for (int i=1; i<=n; i++){
        if (!t[u].ch[ch[i]-'a'])
            t[u].ch[ch[i]-'a']=++tot;
        u=t[u].ch[ch[i]-'a'];
    }
    t[u].cnt++;
}
int merge(int u,int v){
    if (!u||!v) return u|v;
    t[u].cnt+=t[v].cnt;
    for (int i=0; i<26; i++)
        t[u].ch[i]=merge(t[u].ch[i],t[v].ch[i]);
    return u;
}
inline void get_fail(int rt){
    head=1,tail=0;
    for (int i=0; i<26; i++)
        if (t[rt].ch[i]){
            t[rt].ch2[i]=t[rt].ch[i];
            t[t[rt].ch[i]].fail=rt;
            team[++tail]=t[rt].ch[i];
        }
        else t[rt].ch2[i]=rt;
    while (head<=tail){
        int x=team[head];
        for (int i=0; i<26; i++){
            if (t[x].ch[i]){
                t[x].ch2[i]=t[x].ch[i];
                t[t[x].ch[i]].fail=t[t[x].fail].ch2[i];
                team[++tail]=t[x].ch2[i];
            }
            else t[x].ch2[i]=t[t[x].fail].ch2[i];
        }
        t[x].sum=t[x].cnt+t[t[x].fail].sum;
        head++;
    }
}
void insert(int z){
    build_trie(++num[z],z); dg[z][num[z]]=1;
    while (dg[z][num[z]]==dg[z][num[z]-1]&&num[z]>1){
        num[z]--; dg[z][num[z]]+=dg[z][num[z]+1];
        root[z][num[z]]=merge(root[z][num[z]],root[z][num[z]+1]);
    }
    get_fail(root[z][num[z]]);
}
int query(int z){
    int ans=0;
    for (int i=1; i<=num[z]; i++){
        int u=root[z][i];
        for (int j=1; j<=n; j++){
            u=t[u].ch2[ch[j]-'a'];
            ans+=t[u].sum;
        }
    }
    return ans;
}
int main(){
    int op;
    scanf("%d",&q);
while (q--){
    scanf("%d",&op);
    scanf("%s",ch+1); n=strlen(ch+1);
    if (op==1||op==2) insert(op-1);
    if (op==3) printf("%d\n",query(0)-query(1));
    fflush(stdout);
}
    return 0;
}