icontofig | 发布于 2020-02-12 22:36:15 | 阅读量 344 | 字符串
发布于 2020-02-12 22:36:15 | 字符串

题目大意

维护一个集合支持:

1.1. 添加一个模式串。

2.2. 删除一个串。

3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。

题目要求使用fflush(stdout)方法强制在线。

题解

更新了AC自动机内存池回收写法的模板。

多模式串匹配算法,明显的AC自动机的题目。

但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动机里面的fail指针是不支持的,插入字符串只能重新暴力重构fail指针)。

于是考虑建立多个AC自动机,但是很遗憾的是,如果每一次添加or删除操作我们都去建立一个AC自动机,那么查询的时候时间复杂度会炸掉,但是多个AC自动机的做法又不可避免。

所以我们就要想如何优化。

首先将插入和删除分开建AC自动机组是没有任何异议的。最终答案就是在插入的AC自动机组中的答案减去在删除的AC自动机组中的答案。

根据二进制加法(二进制堆的启发式合并)的启发,我们对属于同一种操作的AC自动机进行二进制分组。

我们在动态维护该种操作的时候,将新来的模式串新建一个AC自动机,并设置其数量为1,表示该AC自动机中带有的模式串的数量。

当当前的AC自动机中的模式串数量和前一个AC自动机中模式串数量相等的时候,我们就将两个AC自动机暴力合并。

能证明这样每个字符串最多被加入AC自动机并重构fail的次数在log2n次。

每次查询的时候,只需要将某种操作的AC自动机组中的全体AC自动机全部扫一遍就行了。

注意合并的时候回收空间。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
typedef long long ll;
int st[maxn<<1];
int cnt;
struct trie_node{
    int next[26],fail,end,sum,ac[26];
}tr[maxn<<1];
struct AC_auto{
    int root;
    inline int newnode(){
        int p = st[cnt];
        for(int i = 0;i < 26;++i){
            tr[p].next[i] = -1;
            tr[p].ac[i] = -1;
        }
        tr[p].end = 0;
        tr[p].sum = 0;
        cnt++;
        return p;
    }
    inline void init(){
        root = newnode();
        return;
    }
    inline void insert(char *s){
        int now = root;
        for(int i = 0;s[i];++i){
            if(tr[now].next[s[i] - 'a'] == -1)
                tr[now].next[s[i] - 'a'] = newnode();
            now = tr[now].next[s[i] - 'a'];
        }
        tr[now].end++;
        return;
    }
    inline void build(){
        queue<int>q;
        tr[root].fail = root;
        for(int i = 0;i < 26;++i){
            if(tr[root].next[i] == -1)
                tr[root].ac[i] = root;
            else{
                tr[tr[root].next[i]].fail = root;
                q.push(tr[root].next[i]);
                tr[root].ac[i] = tr[root].next[i];
            }
        }
        while(!q.empty()){
            int now = q.front();
            tr[now].sum = tr[now].end + tr[tr[now].fail].sum;
            q.pop();
            for(int i = 0;i < 26;++i){
                if(tr[now].next[i] == -1)
                    tr[now].ac[i] = tr[tr[now].fail].ac[i];
                else{
                    tr[tr[now].next[i]].fail = tr[tr[now].fail].ac[i];
                    q.push(tr[now].next[i]);
                    tr[now].ac[i] = tr[now].next[i];
                }
            }
        }
        return;
    }
    void merge(int &x,int y){
        if(y == -1)return;
        if(x == -1)
            x = newnode();
        for(int i = 0;i < 26;++i)
            merge(tr[x].next[i],tr[y].next[i]);
        tr[x].end += tr[y].end;
        cnt -= 1;
        st[cnt] = y;
        return;
    }
    ll calc(char *s){
        ll res = 0;
        int now = root;
        for(int i = 0;s[i];++i){
            int x = s[i] - 'a';
            while(now != root && !tr[now].ac[x])
                now = tr[now].fail;
            if(tr[now].ac[x])
                now = tr[now].ac[x];
            res += tr[now].sum;
        }
        return res;
    }
};
struct node{
    int tot;
    int num[20];
    AC_auto ac[20];
    node(){tot = 0;memset(num,0,sizeof(num));}
    void insert(char *s){
        num[++tot] = 1;
        ac[tot].init();
        ac[tot].insert(s);
        while(tot > 1){
            if(num[tot] == num[tot - 1]){
                ac[tot-1].merge(ac[tot-1].root,ac[tot].root);
                num[tot-1] += num[tot];
                num[tot] = 0;
                tot--;
            }
            else break;
        }
        ac[tot].build();
    }
    ll query(char *s){
        ll ret = 0ll;
        for(int i = 1;i <= tot;++i)
            ret += ac[i].calc(s);
        return ret;
    }
}in,out;
char s[maxn];
int m,op;
int main(){
    for(int i = 0;i < (maxn<<1);++i){
        st[i] = i;
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d",&op);
        scanf("%s",s);
        switch(op){
            case 1 : in.insert(s);break;
            case 2 : out.insert(s);break;
            default : printf("%lld\n",in.query(s) - out.query(s));fflush(stdout);break;
        }
    }
    return 0;
}



内容更新于: 2020-02-12 22:36:15
链接地址: http://blog.leanote.com/post/icontofig/CodeForces-710F.-String-Set-Queries

上一篇: Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树

下一篇: CodeForces - 1055F Tree and XOR 01-Trie

344 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航