如果你52

P8306 【模板】字典树

Autumn_Rain @ 2024-10-24 21:28:49

注释掉的初始化方式是错的!!!

#include<bits/stdc++.h>
using namespace std;
int T; 
int n,q;
const int N=3e6+10;
int t[N][70];
int tot;
int word[N];
int num(char x){
    if(x>='A'&&x<='Z')return x-'A';
    if(x>='a'&&x<='z')return x-'a'+26;
    else return x-'0'+52;
} 
void insert(string s){
    int u=0;
    for(int i=0;i<s.size();i++){
        int a=num(s[i]);
        if(!t[u][a])t[u][a]=++tot;
        u=t[u][a];
        word[u]++;
    }
}
int qry(string s){
    int u=0;
    for(int i=0;i<s.size();i++){
        int a=num(s[i]);
        if(t[u][a]==0)return 0;
        u=t[u][a];
    }
    return word[u];
}
void solve(){
//  for(int i=0;i<=tot;i++){
//      word[i]=0;
//      for(int j=1;j<=68;j++){
//          t[i][j]=0;
//      }
//  }
//  tot=0;
    for(int i=0;i<=tot;i++){
        for(int j=0;j<=66;j++){
            t[i][j]=0;
        } 
    } 
    for(int i=0;i<=tot;i++){
        word[i]=0;
    } 
    tot=0;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        insert(s);
    }
    while(q--){
        string s;
        cin>>s;
        cout<<qry(s)<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}

by 210101zhaosicheng @ 2024-11-03 17:09:41

@Autumn_Rain

!! 感谢 dalao


by Autumn_Rain @ 2024-11-03 17:21:50

@210101zhaosicheng 居然可以帮到人hhhc


by SJS_z @ 2024-11-03 18:04:05

真是初始化的问题!!!


|