蒟蒻#2#3#4 WA了,求调

P8306 【模板】字典树

1zhangziheng2023 @ 2024-08-07 11:21:55

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
int n,q,cnt;
int v[3000005],tr[3000005][70];
int turn(char c){
    int b;
    if(c>='a'&&c<='z')b=c-'a';
    else if(c>='A'&&c<='Z')b=c-'A'+26;
    else b=c-'0'+52;
    return b;
}
signed main(){
    cin>>T;
    while(T--){
        for(int i=0;i<=cnt;i++){
            v[i]=0;
            for(int j=1;j<=125;j++){
                tr[i][j]=0;
            }
        }
        cnt=0;
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            int root=0;
            for(int j=0;j<s.size();j++){
                int c=turn(s[j]);
                if(tr[root][c]==0){
                    cnt++;
                    tr[root][c]=cnt;
                    root=cnt;
                }
                else{
                    root=tr[root][c];
                }
                v[root]++;
            }
        }
        while(q--){
            string s;
            cin>>s;
            int root=0;
            bool z=0;
            for(int j=0;j<s.size();j++){
                int c=turn(s[j]);
                if(tr[root][c]==0){
                    z=1;
                    break;
                }
                root=tr[root][c];
            }
            if(z==0)cout<<v[root]<<endl;
            else cout<<0<<endl;
            // for(int i=1;i<=cnt;i++)cout<<v[i]<<' ';
            // cout<<endl;
        }
    }
    return 0;
}

by ilmex @ 2024-08-08 09:29:47

@1zhangziheng2023 tr数组归0时,j从0开始


by 1zhangziheng2023 @ 2024-08-08 09:58:52

@ilmex 已解决,thanks


by 1zhangziheng2023 @ 2024-08-08 09:59:12

已关


by qbzhy08 @ 2024-08-16 14:47:18

@ilmex 为啥从0开始啊,求解释 感觉用不到0啊映射时也没映射到0啊


by letusgo @ 2024-08-29 15:32:00

@qbzhy08 从节点0到a需要tr[0][0]


|