为何不同的写法,不同的结果?

P8306 【模板】字典树

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;
}

|