Trie树（字典树）

原理：

        1. ch[p][j]:p是每个单词存到的idx索引，j是存入字符映射的数字

        2. cnt[p] 存这个单词个数

【模板】字典树 - 洛谷

#include <iostream>
#include <cstring>
using namespace std;const int N = 3e6 + 10;
int ch[N][100], idx;
int cnt[N];
char str[N];int convert(char s) { // 哈希映射if(s >= 'A' && s <= 'Z')return s - 'A';else if(s >= 'a' && s <= 'z')return s - 'a' + 26;else return s - '0' + 52;
}void insert(char s[]) {int p = 0;for(int i = 0; i < strlen(s); i ++ ) {int j = convert(s[i]);if(!ch[p][j]) ch[p][j] = ++ idx;p = ch[p][j];cnt[p] ++;}}int query(char s[]) {int p = 0;for(int i = 0; i < strlen(s); i ++ ) {int j = convert(s[i]);if(!ch[p][j]) return 0;p = ch[p][j];}return cnt[p];
}
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n; cin >> n;while(n -- ) {// 回归初始状态for(int i = 0; i <= idx; i ++ ) {for(int j = 0; j <= 122; j ++ ) {ch[i][j] = 0;}}for(int i = 0; i <= idx; i ++ ) {cnt[i] = 0;}idx = 0;int q, t;cin >> q >> t;for(int i = 1; i <= q; i ++ ) {cin >> str;insert(str);}for(int i = 1; i <= t; i ++ ) {cin >> str;cout << query(str) << endl;}}return 0;
}