蜜汁WA 52pts 求调 悬赏1关注

P8306 【模板】字典树

Shakespeare07 @ 2022-11-02 13:44:06

rt.

#include<bits/stdc++.h>
using namespace std;

#define il inline
#define re register
//#define int long long

il int read(){
    int s=0,w=1;char c=getchar();
    while(!isdigit(c)){ if(c=='-') w=-1;c=getchar();}
    while(isdigit(c)){ s=(s<<3)+(s<<1)+(c^48);c=getchar();}
    return s*w;
}

const int N=1e5+5;

int n,m,cnt[N*30];
char s[N],t[N];

int tot,ch[N*30][65];

il void ins(re char str[]){
    int now=0,len=strlen(str+1);
    for(re int i=1;i<=len;++i){
        int tmp;
        if(str[i]>='a' && str[i]<='z') tmp=str[i]-'a';
        else if(isdigit(str[i])) tmp=str[i]-'0'+52;
        else tmp=str[i]-'A'+26;
        if(!ch[now][tmp]) ch[now][tmp]=++tot;
        now=ch[now][tmp];
        ++cnt[now];
    }
}

il int query(re char str[]){
    int now=0,len=strlen(str+1);
    for(re int i=1;i<=len;++i){
        int tmp;
        if(str[i]>='a' && str[i]<='z') tmp=str[i]-'a';
        else if(isdigit(str[i])) tmp=str[i]-'0'+52;
        else tmp=str[i]-'A'+26;
        if(!ch[now][tmp]) return 0;
        now=ch[now][tmp];
    }
    return cnt[now];
}

il void solve(){
    n=read(),m=read();

    tot=0;
    for(re int i=1;i<=n*30;++i){
        cnt[i]=0;
        for(re int j=0;j<65;++j){
            ch[i][j]=0;
        }
    }

    while(n--){
        scanf("%s",s+1);
        ins(s);
    }
    while(m--){
        scanf("%s",t+1);
        printf("%d\n",query(t));
    }

}

signed main(){
    int T=read();
    while(T--) solve();

    return 0;
}

by WaterSun @ 2022-11-02 13:54:14

你初始化cnt和ch数组要清空到tot啊。


by WaterSun @ 2022-11-02 13:55:10

@aaabbbccc000 改成

for(re int i=0;i<=tot+10;++i){
    cnt[i]=0;
    for(re int j=0;j<65;++j){
        ch[i][j]=0;
    }
}
tot=0;

by Shakespeare07 @ 2022-11-02 15:41:59

@SYC0226 ,谢谢 已关


|