字典树36分求调

P8306 【模板】字典树

_HCl_ @ 2023-10-20 19:13:24

萌新刚学OI,请各位大佬帮忙看一下,低级错误请见谅

#include<bits/stdc++.h>
using namespace std;
int n,q;
int t[3000001][70],cnt[3000001],tot;
int getn(char ch){
    if('a'<=ch&&ch<='z')return ch-'a';
    if('A'<=ch&&ch<='Z')return ch-'a'+26;
    if('0'<=ch&&ch<='9')return ch-'0'+52;
}
void ins(string s){
    int p=0;
    for(int i=0;i<s.length();++i){
        int ch=getn(s[i]);
        if(!t[p][ch])t[p][ch]=++tot;
        p=t[p][ch];
        cnt[p]++;
    }
}
int que(string s){
    int p=0;
    for(int i=0;i<s.length();++i){
        int ch=getn(s[i]);
        if(!t[p][ch])return 0;
        p=t[p][ch];
    }
    return cnt[p];
}
void work(){
    for(int i=0;i<=tot;++i)for(int j=0;j<70;++j)t[i][j]=0;
    for(int i=0;i<=tot;++i)cnt[i]=0;
    tot=0;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        ins(s);
    }
    for(int i=1;i<=q;++i){
        string t;
        cin>>t;
        cout<<que(t)<<"\n";
    }
}
int main(){
    int T;
    cin>>T;
    while(T--)work();
 } 

by wuudii @ 2023-10-20 19:20:13

@HCL,sb,

if('A'<=ch&&ch<='Z')return ch-'a'+26;->if('A'<=ch&&ch<='Z')return ch-'A'+26;


by wuudii @ 2023-10-20 19:22:20

record: https://www.luogu.com.cn/record/130617973


by _HCl_ @ 2023-10-20 20:05:11

@wuudii 好的谢谢 另外膜拜超级大神


|