求调,5-6AC,其余Wa

P8306 【模板】字典树

caohan @ 2023-12-13 21:20:23

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,t,q;
ll cccccnt=0;
ll son[3000005][65];
ll cnt[3000005];
ll get(char x)
{
    if(x<='9'&&x>='0')
    {
        return x-48;
    }
    else if(x<='Z'&&x>='A')
    {
        return x-'A'+10;
    }
    else
    {
        return x-'a'+34;
    }
}
void insert(string s)
{
    int p=0,l=s.size();
    for(int i=0;i<l;i++){
        int c=get(s[i]);
        if(!son[p][c])
            son[p][c]=++cccccnt;
        p=son[p][c];
        cnt[p]++;
    }
}
ll find(string s)
{
    ll p=0,l=s.size();
    for(ll i=0;i<l;i++)
    {
        int c=get(s[i]);
        if(!son[p][c])
        {
            return 0;
        }
        p=son[p][c];
    }
    return cnt[p];
}
string s;
void solve()
{
    cin>>n>>q;
    for(ll i=0;i<=cccccnt;i++)
    {
        for(int j=0;j<=58;j++)
        {
            son[i][j]=0;
        }
        cnt[i]=0;
    }
    cccccnt=0;
    for(ll i=1;i<=n;i++)
    {
        cin>>s;
        insert(s);
    }
    for(ll i=1;i<=q;i++)
    {
        cin>>s;
        cout<<find(s)<<"\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("P8306_1.in","r",stdin);
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

by I_AK_CTSC @ 2023-12-13 21:42:27

我也36过。\ 注意题目:

t_is_j 的前缀的数目,所以不能算 t_i 的前缀


|