CF710F. String Set Queries AC自动机二进制分组

发表于 | 阅读数

一个集合支持三种操作

  • 插入字符串
  • 删除字符串
  • 查询该字符串中集合内字符串出现次数

删除和插入可以建两个$AC$自动机，相减即可。如果查询少，就查询的时候建立$AC$自动机。如果插入少就可以暴力每次建立多个AC自动机。

可是这道题需要动态的，考虑二进制分组。比如$11=1+2+8$,有$11$个字符串的就可以根据有$1$个串的$AC$自动机+有$2$个串的$AC$自动机+有$8$个串的$AC$自动机。插入的时候考虑二进制加法的形式，进位即合并前后字典树。然后暴力建立$AC$自动机。

复杂度

由于$\sum |S|\leq4\times 10^5$，合并$O(|S_i|\log |S_i|)$。查询$O(S_q \log |S_i|)$

代码 
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

const int AN = 3e5 + 100;
struct ACAM
{
    int nxt[N][26], tmp[N][26], fail[AN], rt[30], end[N], sum[N], siz[30];
    int top, acnt;
    ACAM() { top = acnt = 0; }
    void getfail(int root)
    {
        queue<int> q;
        for (int i = 0; i < 26; i++)
        {
            int to = tmp[root][i];
            if (!to)
                nxt[root][i] = root;
            else
            {
                nxt[root][i] = to;
                fail[to] = root;
                q.push(to);
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            sum[u] = end[u] + sum[fail[u]];
            for (int i = 0; i < 26; i++)
            {
                int to = tmp[u][i];
                if (!to)
                    nxt[u][i] = nxt[fail[u]][i];
                else
                {
                    nxt[u][i] = to;
                    fail[to] = nxt[fail[u]][i];
                    q.push(to);
                }
            }
        }
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x | y;
        end[x] += end[y];
        for (int i = 0; i < 26; ++i)
            tmp[x][i] = merge(tmp[x][i], tmp[y][i]);
        return x;
    }
    void insert(char *t)
    {
        int len = strlen(t + 1);
        rt[++top] = ++acnt;
        siz[top] = 1;
        int u = acnt;
        for (int i = 1; i <= len; i++)
        {
            int id = t[i] - 'a';
            if (!tmp[u][id])
                tmp[u][id] = ++acnt;
            u = tmp[u][id];
        }
        end[u] = 1;
        while (top && siz[top] == siz[top - 1])
        {
            top--;
            rt[top] = merge(rt[top], rt[top + 1]);
            siz[top] += siz[top + 1];
            siz[top + 1] = rt[top + 1] = 0;
        }
        getfail(rt[top]);
    }
    int query(char *s)
    {
        int res = 0, n = strlen(s + 1);
        for (int i = 1; i <= top; ++i)
        {
            int cur = rt[i];
            for (int j = 1; j <= n; ++j)
            {
                cur = nxt[cur][s[j] - 'a'];
                res += sum[cur];
            }
        }
        return res;
    }

} t1, t2;

int main()
{
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int op;
        char t[N];
        scanf("%d %s", &op, t + 1);
        if (op == 1)
            t1.insert(t);
        else if (op == 2)
            t2.insert(t);
        else
        {
            printf("%d\n", t1.query(t) - t2.query(t));
        }
        fflush(stdout);
    }
}