字典树 52 分求助

P8306 【模板】字典树

IYSY2009I @ 2022-11-11 21:40:45

RT,另外问一下我这种 700 多 MB 的写法真的有用吗

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
struct tree{
    int son[62];
    int str=0;
};
tree tr[3000005];
char s[3000005];
char abcd;
void cf(){
    int cnt=0;
    int n=read(),q=read();
    for(int i=1;i<=n;i++){
        cin>>s;
        int ls=strlen(s);
        int id=0;
        for(int i=0;i<ls;i++){
            int tmp=(s[i]>='a'&&s[i]<='z')?s[i]-'a':((s[i]>='A'&&s[i]<='Z')?s[i]-'A'+26:s[i]-'0'+52);
            if(tr[id].son[tmp]){
                id=tr[id].son[tmp];
                tr[id].str++;
            }
            else{
                cnt++;
                tr[cnt].str=1;
                tr[id].son[tmp]=cnt;
                id=cnt;
            }
        }
    }
    for(int i=1;i<=q;i++){
        cin>>s;
        int ls=strlen(s);
        int id=0;
        bool flag=1;
        for(int i=0;i<ls;i++){
            int tmp=(s[i]>='a'&&s[i]<='z')?s[i]-'a':((s[i]>='A'&&s[i]<='Z')?s[i]-'A'+26:s[i]-'0'+52);
            if(tr[id].son[tmp]) id=tr[id].son[tmp];
            else{
                printf("0\n");
                flag=0;
                break;
            }
        }
        if(flag) printf("%d\n",tr[id].str);
    }
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<=61;j++)
            tr[i].son[j]=0;
        tr[i].str=0;
    }
    return;
}
int main(){
    int t=read();
    for(int i=1;i<=t;i++)
        cf();
    return 0;
}

by IYSY2009I @ 2022-11-11 21:50:09

不等了,明天再看看


by cancan123456 @ 2022-11-11 21:50:17

map,你值得拥有(虽然查询多个 \log|\Sigma|


by Anonymely @ 2022-11-12 09:37:18

写什么map啊,指针你值得拥有


by weirdoX @ 2022-12-11 13:41:02

初始化 i从0开始!!


by IYSY2009I @ 2023-01-16 18:59:00

@weirdoX 谢谢大佬,AC 了


|