蒟蒻的TLE字典树求助

P8306 【模板】字典树

daitouzero @ 2023-02-02 11:43:28

用指针写的,而且不知道为什么这个字典树占用空间奇大无比

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxwordset=63;
int Hash[256],id;
struct NODE
{
    int cnt;
    bool wordset[maxwordset];
    NODE* son[maxwordset];
    NODE()
    {
        cnt=0;
        memset(wordset,false,sizeof(wordset));
        for (int i=0;i<maxwordset;i++)
            son[i]=NULL;
    }
};
inline void insert(NODE* root,string word)
{
    NODE* temp=root,temp2;
    for (int i=0;i<word.size();i++)
    {
        if (!(temp->wordset[Hash[word[i]]]))
        {
            temp->wordset[Hash[word[i]]]=true;
            temp->son[Hash[word[i]]]=new NODE;
        }
        temp->son[Hash[word[i]]]->cnt++;
        temp=temp->son[Hash[word[i]]];
    }
}
inline int query(NODE* root,string word)
{
    NODE* temp=root,temp2;
    for (int i=0;i<word.size();i++)
    {
        if (!(temp->wordset[Hash[word[i]]])) return 0;
        temp=temp->son[Hash[word[i]]];
    }
    return temp->cnt;
}
void deletetrie(NODE* root)
{
    for (int i=0;i<maxwordset;i++)
        if (root->wordset[i])
            deletetrie(root->son[i]);
    delete root;
}
NODE* root;
string read;
int T,n,q;
int main()
{   
    for(char i='a';i<='z';i++) Hash[i]=++id;
    for(char i='A';i<='Z';i++) Hash[i]=++id;
    for(char i='0';i<='9';i++) Hash[i]=++id;
    cin>>T;
    while (T--)
    {
        root=new NODE;
        cin>>n>>q;
        while (n--)
        {
            cin>>read;
            insert(root,read);
        }
        while (q--)
        {
            cin>>read;
            cout<<query(root,read)<<endl;
        }
        deletetrie(root);
    }
    return 0;
}

|