Trie树 WA36 玄学求调

P8306 【模板】字典树

Mo_Qiong @ 2023-08-05 11:38:02

#include<bits/stdc++.h>
#define N 3000100
using namespace std;
int tr[N][66],sum[N];
int asc(char c){
    if('0'<=c<='9')return c-'0';
    else if('a'<=c<='z')return c-'a'+10;
    else if('A'<=c<='Z')return c-'A'+36;
}
int main(){
    //freopen("_.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        int n,q,num=0;
        scanf("%d%d",&n,&q);
        while(n--){
            string s;
            cin>>s;
            int k=0;
            for(int i=0;i<s.length();i++){
                int c=asc(s[i]);
                if(!tr[k][c])tr[k][c]=++num;
                k=tr[k][c];
                sum[k]++;
            }
        }
        while(q--){
            string s;
            cin>>s;
            int k=0;
            for(int i=0;i<s.length();i++){
                int c=asc(s[i]);
                if(!tr[k][c]){k=tr[k][c];break;}
                //if(!tr[k][c])tr[k][c]=++num; 把上面这一行换成这个后变成20分,但不应该是一样的吗?都不存在了,应该都输出0吧...
                k=tr[k][c];
            }
            cout<<sum[k]<<endl;
        }
        for(int i=0;i<=num;i++){
            sum[i]=0;
            for(int j=1;j<=62;j++)tr[i][j]=0;
        }
    }
    return 0;
}

初始化应该没错,因为第一个点只有1组数据,但还是错了


|