DDOSvoid's Blog

CF 710F String Set Queries

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/710/F

简要题意：有三种操作，操作一向集合中加入一个字符串，操作二从集合中删除一个字符串，操作三给定一个模板串，查询集合中的串在模板串中出现次数的总和

$len\le 3\times 10^5$

Solution

首先能够想到使用 $AC$ 自动机，$AC$​ 自动机可以快速查询一系列串在模板串中的出现次数

但是注意到题目要求动态加入和删除串，我们考虑二进制分组，合并两组的时候可以使用类似线段树合并的东西

删除串我们可以同样看成加入，在查询时减去这些答案即可

时间复杂度 $O(n\log n\sum+n\log ^2n)$​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 300010
#define ll long long
using namespace std;

int n;

char s[maxn];

#define ch s[i] - 'a'
struct Group {
    
    struct Trie {
        int nxt[26], Nxt[26], cnt, Cnt, fail;
    } T[maxn]; int top, rt[maxn], num, sz[maxn];

    void insert(int rt, char *s) {
        int l = strlen(s), now = rt;
        for (int i = 0; i < l; ++i) {
            if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
            now = T[now].nxt[ch];
        } ++T[now].cnt;
    }

    void init_fail(int rt) {
        queue<int> Q;
        for (int i = 0; i < 26; ++i) {
            int u = T[rt].nxt[i]; if (!u) { T[rt].Nxt[i] = rt; continue; }
            T[rt].Nxt[i] = u; T[u].Cnt = T[u].cnt; T[u].fail = rt; Q.push(u); 
        }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop(); 
            for (int i = 0; i < 26; ++i) {
                int v = T[u].nxt[i];
                if (!v) { T[u].Nxt[i] = T[T[u].fail].Nxt[i]; continue; }
                T[u].Nxt[i] = v; T[v].fail = T[T[u].fail].Nxt[i];
                T[v].Cnt = T[v].cnt + T[T[v].fail].Cnt; Q.push(v);
            }
        }
}

    int query(char *s) {
        int l = strlen(s), ans = 0;
        for (int o = 1; o <= num; ++o)
            for (int i = 0, now = rt[o]; i < l; ++i) 
                now = T[now].Nxt[ch], ans += T[now].Cnt;
        return ans;
    }

    void merge(int &i, int j) {
        if (!i) return i = j, void();
        if (!j) return ;
        T[i].cnt += T[j].cnt;
        for (int o = 0; o < 26; ++o) merge(T[i].nxt[o], T[j].nxt[o]); 
    }

    void insert(char *s) {
        rt[++num] = ++top; sz[num] = 1;
        insert(rt[num], s);
        while (sz[num] == sz[num - 1]) merge(rt[num - 1], rt[num]), sz[num - 1] += sz[num], --num;
        init_fail(rt[num]);
    }
} G1, G2;

inline void solve_1() {
    cin >> s;
    G1.insert(s);
}

inline void solve_2() {
    cin >> s;
    G2.insert(s);
}

inline void solve_3() {
    cin >> s;
    cout << G1.query(s) - G2.query(s) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        }
    }
    return 0;
}