WA前四点求助

P8306 【模板】字典树

CRYCHIC_Official @ 2024-06-26 16:01:10

#include<bits/stdc++.h>
using namespace std;
int idx=0;
int cnt[4000000];
int ch[4000000][62];
char s[4000000];
int tota[4000000]= {0};

//字符映射
int y(char t) {
    if(t>='0' && t<='9') {
        return t-0;
    }
    if(t>='A' && t<='Z') {
        return t-'A'+10;
    }
    if(t>='a' && t<='z') {
        return t-'a'+36;
    }

}

//每个点以下有多少个单子(即以某点为根节点的子树上cnt的和)
void tot() {
    for(int i=idx; i>=0; i--) {
        for(int d=0; d<62; d++) {
            tota[i]=tota[i]+tota[ch[i][d]];
        }
    }
}

//插入
void insert(char *s) {
    int p=0;
    for(int i=0; s[i]; i++) {
        int j=y(s[i]);
        if(ch[p][j]==0) {
            idx++;
            ch[p][j]=idx;
        }
        p=ch[p][j];
    }
    cnt[p]++;
    tota[p]++;
}

//查询
int query(char *s) {
    int p=0;
    int ss=0;
    for(int i=0; s[i]; i++) {
        int j=y(s[i]);
        if(ch[p][j]==0) {
            return 0;
        }
        p=ch[p][j];
    }
    return tota[p];
}

int main() {
    int M;
    cin>>M;
    for(int r=1; r<=M; r++) {
        //重置
        for(int i=0; i<=idx; i++) {
            cnt[i]=0;
            for(int ii=0; ii<62; ii++) {
                ch[i][ii]=0;
            }
            tota[i]=0;
        }
        idx=0;
                                    //

        int a,b;
        cin>>a>>b;
        for(int i=1; i<=a; i++) {
            cin>>s;
            insert(s);
        }
        tot();
        for(int i=1; i<=b; i++) {
            cin>>s;
            cout<<query(s)<<endl;
        }
    }

}

by Ravener @ 2024-06-26 18:14:30

不应该是 t-'0' 吗 @Ink_Rain


by CRYCHIC_Official @ 2024-06-26 21:01:30

@Ravener 谢谢,我真是若智


|