为什么这么慢???

P8306 【模板】字典树

Jadonyzx @ 2024-05-31 20:55:39

#include<bits/stdc++.h>
#define maxn 3000010
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        write(-x);
        return;
    }
    if(x>=10)write(x/10);
    putchar(x%10+'0');
    return;
}
int n,q,T,p,len;
char ccf[3000010];
int trie[maxn][150],cnt,siz[maxn];
void init(){
    for(int i=0;i<=cnt;++i){
        for(int j=0;j<=140;++j)
            trie[i][j]=0;
        siz[i]=0;
    }
    cnt=0;return;
}
signed main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    T=read();
    while(T--){
        init();
        n=read();q=read();
        for(int i=1;i<=n;++i){
            cin>>ccf;
            len=strlen(ccf);
            //insert
            p=0;
            for(int j=0;j<len;++j){
                int c=(int)ccf[j];
                if(trie[p][c]==0)trie[p][c]=++cnt;
                p=trie[p][c];
                siz[p]++;
            }
        }
        for(int i=1;i<=q;++i){
            cin>>ccf;
            len=strlen(ccf);
            //find
            p=0;bool f=1;
            for(int j=0;j<len;++j){
                int c=(int)ccf[j];
                if(!trie[p][c]){f=0;break;}
                p=trie[p][c];
            }
            if(f)cout<<(siz[p]);
            else cout<<(0);
            cout<<('\n');
        }
    }
    return 0;
}

by supernoobbb @ 2024-07-11 20:19:04

插个眼,我也慢,#1压线911ms过的


|