1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接保存所有模式串。
// 每次查询时暴力统计有多少个模式串以查询串作为前缀。

bool is_prefix(const string &pre, const string &s) {
    if ((int) pre.size() > (int) s.size()) {
        return false;
    }
    for (int i = 0; i < (int) pre.size(); i++) {
        if (pre[i] != s[i]) {
            return false;
        }
    }
    return true;
}

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

    int T;
    cin >> T;

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

        vector<string> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        for (int i = 1; i <= q; i++) {
            string s;
            cin >> s;
            int ans = 0;
            for (int j = 0; j < n; j++) {
                if (is_prefix(s, a[j])) {
                    ans++;
                }
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 3200005;

int head[MAXNODE];       // head[u] 表示节点 u 的第一条出边
int to[MAXNODE];         // 边的终点
int nxt[MAXNODE];        // 邻接表下一条边
unsigned char ch[MAXNODE]; // 这条边对应哪个字符编号
int cnt[MAXNODE];        // 经过这个节点的模式串数量

int node_cnt = 0;
int edge_cnt = 0;

int new_node() {
    ++node_cnt;
    return node_cnt;
}

// 把字符映射到 0..61
int trans(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    }
    if (c >= 'A' && c <= 'Z') {
        return c - 'A' + 10;
    }
    return c - 'a' + 36;
}

// 在节点 u 的所有出边里寻找字符 code 对应的儿子。
int find_child(int u, int code) {
    for (int i = head[u]; i != 0; i = nxt[i]) {
        if ((int) ch[i] == code) {
            return to[i];
        }
    }
    return 0;
}

int add_child(int u, int code) {
    int v = new_node();
    ++edge_cnt;
    to[edge_cnt] = v;
    ch[edge_cnt] = (unsigned char) code;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    return v;
}

void insert_string(int root, const string &s) {
    int p = root;
    for (int i = 0; i < (int) s.size(); i++) {
        int code = trans(s[i]);
        int v = find_child(p, code);
        if (v == 0) {
            v = add_child(p, code);
        }
        p = v;
        cnt[p]++; // 经过这个节点的字符串数量，也就是这个前缀的出现次数
    }
}

int query_prefix_count(int root, const string &s) {
    int p = root;
    for (int i = 0; i < (int) s.size(); i++) {
        int code = trans(s[i]);
        p = find_child(p, code);
        if (p == 0) {
            return 0;
        }
    }
    return cnt[p];
}

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

    int T;
    cin >> T;

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

        int root = new_node();

        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            insert_string(root, s);
        }

        for (int i = 1; i <= q; i++) {
            string s;
            cin >> s;
            cout << query_prefix_count(root, s) << '\n';
        }
    }

    return 0;
}