求调,第3,4,5个点TLE了

P8306 【模板】字典树

fangminding @ 2024-01-23 15:58:44

代码:

#include <bits/stdc++.h>
using namespace std;
int trie[3000007][70];
int cnt[3000007];
int T,n,q;
char tmp[3000006];
int mp[139];
int haveu=1;

void add(char ss[])
{
    int hav=1;
    int lss = strlen(ss);
    for(int i = 0;i <lss;i++)
    {
        int ntmp = mp[ss[i]];
        if(!trie[hav][ntmp])
            trie[hav][ntmp]=++haveu;
        hav=trie[hav][ntmp];
        cnt[hav]++; 
    }
}

int find(char ss[])
{
    int hav=1;
    int lss = strlen(ss);
    for(int i = 0;i <lss;i++)
    {
        int ntmp = mp[ss[i]];
        if(!trie[hav][ntmp])
            return 0;
        hav=trie[hav][ntmp];
    }
    return cnt[hav];
}

int main()
{
    int nIndx = 0;
    for(char i ='0';i<='9';i++)
        mp[i]=nIndx++;
    for(char i ='A';i<='Z';i++)
        mp[i]=nIndx++;
    for(char i ='a';i<='z';i++)
        mp[i]=nIndx++;

    cin>>T;
    for(int asdf = 1;asdf <=T;asdf++)
    {
        cin>>n>>q;
        for(int i = 0;i <haveu;i++)
            for(int j = 0;j <70;j++)
                trie[i][j]=0;
        for(int i = 0;i <haveu;i++)cnt[i]=0;
        for(int i = 1;i <=n;i++)
        {
            scanf("%s",tmp);
            add(tmp);
        }
        for(int i = 1;i <=q;i++)
        {
            scanf("%s",tmp);
            printf("%d\n",find(tmp));
        }
    }
}

不胜感激!


by chenzhiyv @ 2024-01-30 09:44:37

@fangminding 你好像没有清空“haveu”这个变量


by fangminding @ 2024-01-30 09:55:35

已 AC ,感谢!


by fangminding @ 2024-08-30 11:29:43

此帖结


|