YONIC @ 2022-10-14 16:48:15
#include<bits/stdc++.h>
using namespace std;
int t,n,q,tot,trie[(int)(3e6+3)][63],cnt[(int)(3e6+3)],id,g[128];
void insert(string x){
int u=1;
for(int i=0;i<x.length();++i){
if(!trie[u][g[x[i]]]) trie[u][g[x[i]]]=++tot;
u=trie[u][g[x[i]]];
++cnt[u];
}
}
int find(string x){
int u=1;
for(int i=0;i<x.length();++i){
if(!trie[u][g[x[i]]]) return 0;
u=trie[u][g[x[i]]];
}
return cnt[u];
}
int main(){
scanf("%d",&t);
for(int i=48;i<=122;++i) if(isalpha(i)||isdigit(i)) g[i]=id++;
while(t--){
scanf("%d%d",&n,&q);
tot=0;
memset(trie,0,sizeof(trie));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;++i){
string x;
cin>>x;
insert(x);
}
for(int i=1;i<=q;++i){
string x;
cin>>x;
printf("%d\n",find(x));
}
}
return 0;
}
by asasas @ 2022-10-14 16:51:26
@YONIC 您可以把g[i]换成一个函数
int idx(char x){
if(x>='A'&&x<='Z') return x-'A';
else if(x>='a'&&x<='z') return x-'a'+26;
else return x-'0'+52;
}
by asasas @ 2022-10-14 16:52:24
@YONIC u好像应该从0开始,另外这边建议用char,string太慢了
by Eafoo @ 2022-10-14 16:52:37
@YONIC 25行改为 tot = 1
by Eafoo @ 2022-10-14 16:53:41
@YONIC 不要直接memset,应该在 trie 树里递归清空节点
by asasas @ 2022-10-14 16:54:48
@YONIC 可以从0~tot清空trie数组
by YONIC @ 2022-10-14 16:55:38
@Eafoo @asasas 谢谢
by YONIC @ 2022-10-14 16:57:43
@asasas 但是现在长这样 https://www.luogu.com.cn/record/89820261
by asasas @ 2022-10-14 17:01:47
@YONIC https://www.luogu.com.cn/record/89821077
by YONIC @ 2022-10-14 17:01:52
已解决(初始化问题)