救救这孩子吧,快崩溃了!!!

P8306 【模板】字典树

IAKIOI66666 @ 2024-06-10 13:42:00

#include<bits/stdc++.h>
using namespace std;
int k,n,m,ans,t[100050][80],cnt[100050];
string s;
int cmp(char c){
    if(c<='Z'&&c>='A')return c-'A';
    if(c<='z'&&c>='a')return c-'a'+26;
    else return c-'0'+52;
}
void insert(string s){
    int p=0;
    for(int i=0;i<s.length();i++){
        int x=cmp(s[i]);
        if(t[p][x]==0)t[p][x]=++ans;
        p=t[p][x];
        cnt[p]++;
    }
}
int find(string s){
    int p=0;
    for(int i=0;i<s.length();i++){
        int x=cmp(s[i]);
        if(t[p][x]==0)return 0;
        p=t[p][x];
    }
    return cnt[p];
}

int main(){
    cin>>k;
    while(k--){
        memset(t,0,sizeof(t));
        memset(cnt,0,sizeof(cnt));
        ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>s;
            insert(s);
        }
        for(int i=1;i<=m;i++){
            cin>>s;
            cout<<find(s)<<"\n";
        }
    }
    return 0;
}

by IAKIOI66666 @ 2024-06-10 13:45:21

我已经崩溃了,医院开出的证明


by cosf @ 2024-06-10 13:46:16

数组太小,memset 太慢。


by IAKIOI66666 @ 2024-06-10 13:52:24

@cosf :三克油


|