结构体封装的trie
之前TLE了很多次
原因是因为cnt用完没清空...
#include <bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N=3e6+10;
il int read() {
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
il int get_num(char x) {
if(x>='A'&&x<='Z') return x-'A';
if(x>='a'&&x<='z') return x-'a'+26;
if(x>='0'&&x<='9') return x-'0'+52;
}
struct trie {
int q[N][66],cnt,ch[N];
il void clear() {
for(re int i=0; i<=cnt; i++) {
for(int j=0; j<=64; j++) q[i][j]=0;
ch[i]=0;
}
cnt=0;//就是这里
}
il void insert(int len,char *s) {
int nxt=0;
for(re int i=0; i<len; i++) {
int j=get_num(s[i]);
if(!q[nxt][j]) q[nxt][j]=++cnt;
nxt=q[nxt][j];
ch[nxt]++;
}
}
il int query(int len,char *sub) {
int nxt=0;
for(re int i=0; i<len; i++) {
int j=get_num(sub[i]);
if(!q[nxt][j]) return 0;
nxt=q[nxt][j];
}
return ch[nxt];
}
} p;
int T,n,q;
char s[N],sub[N];
int main() {
T=read();
while(T--) {
n=read();
q=read();
p.clear();
for(re int i=1; i<=n; i++) {
cin>>s;
int len=strlen(s);
p.insert(len,s);
}
for(re int i=1; i<=q; i++) {
cin>>sub;
int len=strlen(sub);
int ans=p.query(len,sub);
printf("%d\n",ans);
}
}
return 0;
}