CF710F String Set Queries

我的第一篇黑题题解,应该好好庆祝。

题目大意

给定一个字符串集合,支持的操作有插入,删除和查询给定字符串在给出的模板字符串出现的次数。

操作数 \(m \leq 3 \times 10^5\),输入字符串总长度 \(\sum |s_i| \leq 3\times 10^5\)

本题强制在线。

解题思路

首先看到多模式匹配字符串应该想到 AC 自动机。

关于 AC 自动机,可以参考我的博客,点这里

先考虑删除操作,再开一个 AC 自动机记录删除的串,两个 query 的结果相减即可(满足相减性)。

再考虑插入操作,每次插入都要改 fail 指针,这意味着我们每次插入需要 \(O(n)\),怎么办?

考虑优化每次插入对应 AC 自动机的节点个数,可将 AC 自动机进行二进制分组。

例,已经插入 \(15\) 个字符串,则有 \(5\)AC 自动机,每个 AC 自动机对应的字符串个数分别为 \(8\)\(4\)\(2\)\(1\)

假设现在又要插入一个字符串,则 AC 自动机会合并成 \(1\) 个,对应的字符串个数为 \(16\)

说实话这有点像那个 2048 小游戏。

因为二进制分组保证了每个节点的更新次数只有 \(\log n\) 次,最多维护 \(\log n\) 个块,顾时间复杂度为 \(O(m n \log n)\)

AC CODE

小细节:应在每次输出后调用 fflush(stdout)(然而我也不知道为什么)

#include <bits/stdc++.h>
using namespace std;

const int _ = 6e5 + 5;

struct AC
{
    int tot, val[_], sum[_], fail[_], c[_][26], ch[_][26];
    int id, cnt, rt[_], siz[_];

    void ins(char *s, int len, int k)
    {
        int now = k;
        for (int i = 0; i < len; i++)
        {
            int v = s[i] - ‘a‘;
            if (!c[now][v])
                c[now][v] = ++tot;
            now = c[now][v];
        }
        val[now]++;
    }

    void get_fail(int s)
    {
        fail[s] = s;
        queue<int> q;
        for (int i = 0; i < 26; i++)
            if (c[s][i])
            {
                ch[s][i] = c[s][i];
                q.push(c[s][i]);
                fail[ch[s][i]] = s;
            }
            else
                ch[s][i] = s;
        while (!q.empty())
        {
            int k = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (c[k][i])
                {
                    ch[k][i] = c[k][i];
                    fail[c[k][i]] = ch[fail[k]][i];
                    q.push(c[k][i]);
                }
                else
                    ch[k][i] = ch[fail[k]][i];
            }
            sum[k] = val[k] + sum[fail[k]];
        }
    }

    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        val[x] += val[y];
        for (int i = 0; i < 26; i++)
            c[x][i] = merge(c[x][i], c[y][i]);
        return x;
    }

    void insert(char *s, int len)
    {
        rt[++cnt] = ++id;
        siz[cnt] = 1;
        ins(s, len, rt[cnt]);
        while (siz[cnt] == siz[cnt - 1])
        {
            cnt--;
            siz[cnt] *= 2;
            rt[cnt] = merge(rt[cnt], rt[cnt + 1]);
        }
        get_fail(rt[cnt]);
    }

    int query(char *s, int len)
    {
        int now = 0, ans = 0;
        for (int i = 1; i <= cnt; i++)
        {
            now = rt[i];
            for (int j = 0; j < len; j++)
            {
                now = ch[now][s[j] - ‘a‘];
                ans += sum[now];
            }
        }
        return ans;
    }

} A, B;

int T, op, len;
char c[_];

signed main()
{
    A.tot = B.tot = 3e5 + 1;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%s", &op, c);
        len = strlen(c);
        if (op == 1)
            A.insert(c, len);
        if (op == 2)
            B.insert(c, len);
        if (op == 3)
            printf("%d\n", A.query(c, len) - B.query(c, len));
        fflush(stdout);
    }
    return 0;
}

CF710F String Set Queries

上一篇:二、kafka的环境部署+命令行


下一篇:antd Select(下拉弹框类)组件页面滚动时,下拉内容与弹出父组件分离