为什么超时了??

P8306 【模板】字典树

elpsconr @ 2024-05-14 22:18:47

为什么我用memset会超时??

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+6;
typedef long long ll;
int n,q,idx,trie[N][63],st[N];
char s[N];
map<char,int> v;
void insert(char s[])
{
    int len=strlen(s),p=0;
    for(int i=0;i<len;++i)
    {
        if(!trie[p][v[s[i]]]) trie[p][v[s[i]]]=++idx;
        p=trie[p][v[s[i]]];st[p]++;
    }
}
int query(char s[])
{
    int len=strlen(s),p=0;
    for(int i=0;i<len;++i)
    {
        if(!trie[p][v[s[i]]]) return 0;
        p=trie[p][v[s[i]]];
    }
    return st[p];
}
void solve()
{
    cin>>n>>q;
    memset(st,0,sizeof st);
    memset(trie,0,sizeof trie);
    // for(int i=0;i<=idx;i++)
    // {
    //  st[i]=0;
    //  for(int j=0;j<=62;j++)
    //  {
    //      trie[i][j]=0;
    //  }
    // }
    idx=0;
    for(int i=0;i<n;++i)
    {
        cin>>s;insert(s);
    }
    for(int i=0;i<q;++i)
    {
        cin>>s;
        cout<<query(s)<<endl;
    }
}
int main()
{
   cin.tie(0)->sync_with_stdio(0);
   int t;cin>>t;
   for(char i='a';i<='z';++i) v[i]=++idx;
   for(char i='A';i<='Z';++i) v[i]=++idx;
   for(char i='0';i<='9';++i) v[i]=++idx;
   while(t--)
   solve();
   return 0;
}

by lkjlkjlkj2012 @ 2024-05-22 18:21:29

就是这样,也许memset复杂度高


|