A1687 【模板】字典树

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

// 字典树（Trie）。
//
// 每个节点记录：以它为前缀的模式串个数 cnt。
// 查询串 t 的答案 = 沿着 t 在 Trie 上走到的那个节点的 cnt；
// 走不到（某一步没有对应儿子）说明没有模式串以 t 为前缀，答案是 0。
//
// 内存考虑：所有字符串总长不超过 3e6，节点数可达 3e6。
// 每个节点开 62 个儿子指针要 744MB，超过内存限制，
// 所以这里用「第一个儿子 + 下一个兄弟」的稀疏表示：一个节点一个指针，
// 找儿子时在兄弟链上线性扫（字母表固定 62，链长不超过 62，是常数）。
const int MAXNODE = 3000005;

struct Node {
    int child;    // 第一个儿子，0 表示没有
    int brother;  // 下一个兄弟
    int cnt;      // 以本节点为前缀的模式串个数
    char ch;      // 从父亲走到本节点的字符
};

Node tr[MAXNODE];
int tot = 0;  // 0 号节点是根

// 在 u 的儿子里找字符 c，找不到返回 -1
int getChild(int u, char c) {
    for (int v = tr[u].child; v; v = tr[v].brother) {
        if (tr[v].ch == c) return v;
    }
    return -1;
}

// 新建一个字符为 c 的儿子挂到 u 下面
int newNode(int u, char c) {
    int v = ++tot;
    tr[v].child = 0;
    tr[v].brother = tr[u].child;
    tr[v].cnt = 0;
    tr[v].ch = c;
    tr[u].child = v;
    return v;
}

// 插入一个模式串：沿途每个节点的 cnt 加 1
void insert(const string& s) {
    int u = 0;
    tr[u].cnt++;
    for (char c : s) {
        int v = getChild(u, c);
        if (v == -1) v = newNode(u, c);
        u = v;
        tr[u].cnt++;
    }
}

// 查询：有多少个模式串以 s 为前缀
int query(const string& s) {
    int u = 0;
    for (char c : s) {
        int v = getChild(u, c);
        if (v == -1) return 0;
        u = v;
    }
    return tr[u].cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;

        // 每组数据重新建一棵 Trie
        tot = 0;
        tr[0].child = 0;
        tr[0].brother = 0;
        tr[0].cnt = 0;
        tr[0].ch = 0;

        string s;
        for (int i = 0; i < n; i++) {
            cin >> s;
            insert(s);
        }
        for (int i = 0; i < q; i++) {
            cin >> s;
            cout << query(s) << "\n";
        }
    }
    return 0;
}