1 条题解

  • 0
    @ 2023-3-17 17:11:42
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 50000;
    const int MAXM = 50000;
    const int MAXNODE = 500000; // 单词数*单词长度(最坏情况下节点数量)
    int tot, root, son[MAXNODE + 5][2];
    int tag[MAXNODE + 5]; // 该节点存在几个单词
    int cnt[MAXNODE + 5]; // 该节点下面一共存在几个单词
    void clearNode(int nId)
    {
        for (int i = 0; i < 2; i++)
            son[nId][i] = 0;
        tag[nId] = 0;
    }
    void ins(const string &s)
    {
        int now = root;
        for (int i = 0; i < s.length(); i++)
        {
            int j = s[i] - '0';
            if (!son[now][j])
            {
                son[now][j] = ++tot;
                clearNode(tot);
            }
            now = son[now][j];
            cnt[now]++; // 沿路加
        }
        tag[now]++; // 只加一次
    }
    int check(const string &s)
    {
        int res = 0;
        int now = root;
        for (int i = 0; i < s.length(); i++)
        {
            int j = s[i] - '0';
            if (!son[now][j])
            {
                return res;
            }
            now = son[now][j];
            res += tag[now];
        }
        return res - tag[now] + cnt[now];
    }
    int n, m;
    string b[MAXN + 5];
    string c[MAXM + 5];
    int ans[MAXM + 5];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        // 输入
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            int len;
            char x;
            b[i] = "";
            cin >> len;
            while (len--)
            {
                cin >> x;
                b[i] = b[i] + x;
            }
        }
        for (int i = 1; i <= m; i++)
        {
            int len;
            char x;
            c[i] = "";
            cin >> len;
            while (len--)
            {
                cin >> x;
                c[i] = c[i] + x;
            }
        }
        // 信息放入字典树
        for (int i = 1; i <= n; i++)
            ins(b[i]);
        // 计算每个密码匹配哪些
        for (int i = 1; i <= m; i++)
            cout << check(c[i]) << "\n";
        return 0;
    }
    
    • 1

    「一本通 2.3 练习 3」Secret Message 秘密信息

    信息

    ID
    696
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    32
    已通过
    15
    上传者