悬赏 2 关注请教一下 Trie 树为什么 0 分

P8306 【模板】字典树

YONIC @ 2022-10-14 16:48:15

#include<bits/stdc++.h>
using namespace std;
int t,n,q,tot,trie[(int)(3e6+3)][63],cnt[(int)(3e6+3)],id,g[128];
void insert(string x){
    int u=1;
    for(int i=0;i<x.length();++i){
        if(!trie[u][g[x[i]]]) trie[u][g[x[i]]]=++tot;
        u=trie[u][g[x[i]]];
        ++cnt[u];
    }
}
int find(string x){
    int u=1;
    for(int i=0;i<x.length();++i){
        if(!trie[u][g[x[i]]]) return 0;
        u=trie[u][g[x[i]]];
    }
    return cnt[u];
}
int main(){
    scanf("%d",&t);
    for(int i=48;i<=122;++i) if(isalpha(i)||isdigit(i)) g[i]=id++;
    while(t--){
        scanf("%d%d",&n,&q);
        tot=0;
        memset(trie,0,sizeof(trie));
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i){
            string x;
            cin>>x;
            insert(x);
        }
        for(int i=1;i<=q;++i){
            string x;
            cin>>x;
            printf("%d\n",find(x));
        }
    }
    return 0;
}

by asasas @ 2022-10-14 16:51:26

@YONIC 您可以把g[i]换成一个函数

int idx(char x){
    if(x>='A'&&x<='Z') return x-'A';
    else if(x>='a'&&x<='z') return x-'a'+26;
    else return x-'0'+52;
} 

by asasas @ 2022-10-14 16:52:24

@YONIC u好像应该从0开始,另外这边建议用char,string太慢了


by Eafoo @ 2022-10-14 16:52:37

@YONIC 25行改为 tot = 1


by Eafoo @ 2022-10-14 16:53:41

@YONIC 不要直接memset,应该在 trie 树里递归清空节点


by asasas @ 2022-10-14 16:54:48

@YONIC 可以从0~tot清空trie数组


by YONIC @ 2022-10-14 16:55:38

@Eafoo @asasas 谢谢


by YONIC @ 2022-10-14 16:57:43

@asasas 但是现在长这样 https://www.luogu.com.cn/record/89820261


by asasas @ 2022-10-14 17:01:47

@YONIC https://www.luogu.com.cn/record/89821077


by YONIC @ 2022-10-14 17:01:52

已解决(初始化问题)


|