36tps求助

P8306 【模板】字典树

ace_yulong @ 2024-07-17 15:04:11

求助谢谢

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int n,q,T,t,vis[N][30],sum[N],cnt;
string s;
int gn(char x){//给每个字符一个数字编号 
    if (x>='A'&&x<='Z'){
        return x-'A';
    } 
    if (x>='a'&&x<='z'){
        return x-'a'+26;
    }
    return x-'0'+52;
}
void is(string s){//加入新的字符串
    int pl=0,len=s.size();
    for (int i=0;i<len;i++){
        int c=gn(s[i]);
        if (!vis[pl][c]) vis[pl][c]=++cnt;
        pl=vis[pl][c];
        sum[pl]++;
    } 
}
int find(string s){//寻找字符串
    int pl=0,len=s.size();
    for (int i=0;i<len;i++){
        int c=gn(s[i]);
        if (!vis[pl][c]) return 0;
        pl=vis[pl][c];
    } 
    return sum[pl];
}
int main(){
    cin>>T;
    while(T--){
        for (int i=0;i<=cnt;i++){
            for (int j=0;j<=200;j++){
                vis[i][j]=0;
            }
        }
        for (int i=0;i<=cnt;i++){
            sum[i]=0;
        }
        cnt=0;
        cin>>n>>q;
        for (int i=1;i<=n;i++){
            cin>>s;
            is(s);
        }
        for (int i=1;i<=q;i++){
            cin>>s;
            cout<<find(s)<<"\n";
        }
    }
    return 0;
}

by ace_yulong @ 2024-07-17 15:04:38

@Genius_Star


by ace_yulong @ 2024-07-17 15:10:42

我智了,vis数组第二维开小了,此帖结


by Genius_Star @ 2024-07-17 15:10:51

@ace_yulong 不是,黄题都求助


by ace_yulong @ 2024-07-17 15:18:40

不是你。。。。


|