trie炸,WA#2#3#4

P8306 【模板】字典树

MornHus @ 2023-03-07 21:49:52


#include<bits/stdc++.h>
using namespace std;
int trie[3000001][65];
int T;
int n,q;
int idx;
char a[3000001];
int tot[3000001];
inline int su(char c){
    if(c>='A'&&c<='Z'){
        return c-'A';
    }else if(c>='a'&&c<='z'){
        return c-'a'+26;
    }else{
        return c-'0'+52;
    }
}
inline void insert(char str[]){
    int now=0;
    int leng=strlen(str);
    for(int i=0;i<leng;i++){
        int sus=su(str[i]);
        if(!trie[now][sus]){
            trie[now][sus]=++idx;
        }
        now=trie[now][sus];
        tot[now]++;
    }
}
int find(char str[]){
    int now=0;
    int leng=strlen(str);
    for(int i=0;i<leng;i++){
        int sus=su(str[i]);
        if(!trie[now][sus]){
            return 0;
        }
        now=trie[now][sus];
    }
    return tot[now];
}
inline void clear(){
    for(int i=0;i<=idx;i++){
        for(int j=1;j<=64;j++){
            trie[i][j]=0;
        }
    }
    for(int i=0;i<=idx;i++){
        tot[i]=0;
    }
    idx=0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        clear();
        scanf("%d %d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",a);
            insert(a);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",a);
            printf("%d\n",find(a)); 
        }
    }
    return 0;
}

by bamboo12345 @ 2023-03-07 21:54:22

@MornHus 你是有0的啊


by qiyi0918 @ 2023-07-28 10:12:17

clear函数:trie[x][0]是有值的,也要清空


|