Link_Cut_Y @ 2022-10-06 21:10:25
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000010;
char str[N];
int idx, n, m, T, cnt;
unordered_map<char, int> Map;
struct Trie {
int s[70], val;
void clear() {
memset(s, 0, sizeof s);
val = 0;
}
}tr[N];
int id(char x) { return Map[x]; }
void clear() {
for (int i = 0; i <= idx; i ++ )
tr[i].clear();
idx = 0;
}
void insert(char *str, int len) {
int u = 0;
for (int i = 0; i < len; i ++ ) {
int v = id(str[i]);
if (!tr[u].s[v]) tr[u].s[v] = ++ idx;
u = tr[u].s[v];
}
tr[u].val ++ ;
}
void dfs(int u) {
for (int i = 0; i < cnt; i ++ )
if (tr[u].s[i]) {
dfs(tr[u].s[i]);
tr[u].val += tr[tr[u].s[i]].val;
}
}
int query(char *str, int len) {
int u = 0;
for (int i = 0; i < len; i ++ ) {
int v = id(str[i]);
if (!tr[u].s[v]) return 0;
u = tr[u].s[v];
}
return tr[u].val;
}
void init() {
for (char i = '0'; i <= '9'; i ++ ) Map[i] = cnt ++ ;
for (char i = 'a'; i <= 'z'; i ++ ) Map[i] = cnt ++ ;
for (char i = 'A'; i <= 'Z'; i ++ ) Map[i] = cnt ++ ;
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("my.out", "w", stdout);
scanf("%d", &T);
init();
while (T -- ) {
clear();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%s", str), insert(str, strlen(str));
dfs(0);
while (m -- ) {
scanf("%s", str);
printf("%d\n", query(str, strlen(str)));
}
}
return 0;
}
by _cyh0412_ @ 2022-10-06 21:12:57
数组小不小
by Link_Cut_Y @ 2022-10-06 21:13:48
@cyh0412 找到锅了,
by _cyh0412_ @ 2022-10-06 21:19:10
@Mount_
是不是给个关注啥的
by Link_Cut_Y @ 2022-10-06 21:57:41
@cyh0412 已经关注了,互关吧
by _cyh0412_ @ 2022-10-06 22:06:00
@Mount_ 关了