cbkxx @ 2024-08-15 22:43:13
这是我原来WA36pts的代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
int son[70];
}tree[3000005];
int T,n,q,cnt,ans[3000005],len,pos;
char tmp[3000005];
int f(char x){
if(x>='0'&&x<='9')return x-'0';
if(x>='A'&&x<='Z')return x-'A'+10;
return x-'a'+36;
}
void ins(int x,int wei){
ans[x]++;
if(wei==len-1){
return;
}
int y=f(tmp[wei]);
if(!tree[x].son[y]){
tree[x].son[y]=++cnt;
}
ins(tree[x].son[y],wei+1);
}
int ask(int x,int wei){
if(wei==len-1)return ans[x];
int y=f(tmp[wei]);
if(tree[x].son[y]){
return ask(tree[x].son[y],wei+1);
}
return 0;
}
int main(){
cin>>T;
while(T--){
cnt=pos+1;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%s",tmp);
len=strlen(tmp);
ins(pos+1,0);
}
for(int i=1;i<=q;i++){
scanf("%s",tmp);
len=strlen(tmp);
printf("%d\n",ask(pos+1,0));
}
pos=cnt;
}
return 0;
}
我是在调不出来,就换了一种写法,却就A了
#include<bits/stdc++.h>
using namespace std;
struct node{
int son[70];
}tree[3000005];
int T,n,q,cnt,ans[3000005],pos;
char tmp[3000005];
int f(char x){
if(x>='0'&&x<='9')return x-'0';
if(x>='A'&&x<='Z')return x-'A'+10;
return x-'a'+36;
}
void ins(char tmp[]){
int len=strlen(tmp),now=pos+1;
for(int i=0;i<len;i++){
ans[now]++;
int x=f(tmp[i]);
if(!tree[now].son[x]){
tree[now].son[x]=++cnt;
}
now=tree[now].son[x];
}
ans[now]++;
}
int ask(char tmp[]){
int len=strlen(tmp),now=pos+1;
for(int i=0;i<len;i++){
int x=f(tmp[i]);
if(!tree[now].son[x]){
return 0;
}
now=tree[now].son[x];
}
return ans[now];
}
int main(){
cin>>T;
while(T--){
cnt=pos+1;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%s",tmp);
ins(tmp);
}
for(int i=1;i<=q;i++){
scanf("%s",tmp);
printf("%d\n",ask(tmp));
}
pos=cnt;
}
return 0;
}