悬关求调

RT

提交

// Problem: P8306 【模板】字典树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8306
// Memory Limit: 1 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define fst                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define f(x, y, z) for (register ll x = (y); x <= (z); x++)
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f, N = 3e6 + 10;
ll T;
ll n, q;
namespace Trie
{
ll sz = 0, S[N];
unordered_map<char, ll> M[N];
void insert(string &s)
{
    ll p = 0;
    for (auto i : s)
    {
        if (M[p][i])
        {
            //S[p]++;
            p = M[p][i];
        }
        else
        {
            p = M[p][i] = ++sz;
            //S[p]++;
        }
        S[p]++;
    }
}
ll query(string &s)
{
    ll p = 0;
    for (auto i : s)
    {
        if (M[p][i])
        {
            S[p]++;
            p = M[p][i];
        }
        else
        {
            return 0;
        }
    }
    return S[p];
}
void clear()
{
    f(i, 0, sz + 1) //
    {
        M[i].clear();
        S[i] = 0;
    }
    sz = 0;
}
} // namespace Trie
string S;
signed main()
{
    fst;
    cin >> T;
    while (T--)
    {
        cin >> n >> q;
        f(i, 1, n)
        {
            cin >> S;
            Trie::insert(S);
        }
        f(i, 1, q)
        {
            cin >> S;
            cout << Trie::query(S) << endl;
        }
        Trie::clear();
    }
    return 0;
}