36pts求调

P8306 【模板】字典树

0X0002M @ 2023-09-21 22:01:50

T了4个点

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

int son[3000010][80], cnt[3000010], idx = 0;
void insert(string str)
{
    int p = 0;
    for(int i = 0;i < str.size();i++)
    {
        int u = str[i] - '0';
        if(!son[p][u])
        son[p][u] = ++idx;
        p = son[p][u];
        cnt[p]++;
    }
}

int query(string str)
{
    int p = 0;
    for(int i = 0;i < str.size();i++)
    {
        int u = str[i] - '0';
        if(!son[p][u])
        return 0;
        p = son[p][u];
    }

    return cnt[p];
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        idx = 0;
        memset(son, 0, sizeof(son));
        memset(cnt, 0, sizeof(cnt));

        int n, m, ans = 0;
        cin >> n >> m;
        for(int i = 0;i < n;i++)
        {
            string str;
            cin >> str;
            insert(str);
        }
        for(int i = 0;i < m;i++)
        {
            string str;
            cin >> str;
            cout << query(str) << endl;
        }
    }
    return 0;
}

by zimmy @ 2023-10-20 11:20:27

这题用memset初始化会tle,你每次只将son和cnt下标为0到idx的地方赋为0试试


|