Trie 32分 板子求助!!悬赏一关注!!MnZn刚学OI一毫秒。

P8306 【模板】字典树

刘辰雨 @ 2022-11-30 18:12:43

rt

#include <iostream>
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;

long long T;
long long N,Q;
long long A[3000006][75],tot;
long long Num[3000006];
bitset<3000006> End;

char s[3000006];

int ChangeBack(char a)
{
    if('0' <= a && a <= '9')
        return a-'0';
    if('A' <= a && a <= 'Z')
        return a-55;
    if('a' <= a && a <= 'z')
        return 35+a-'a';
} 

void Insert(char s[])
{
    long long now = 0;
    long long len = strlen(s);
    for(long long i = 0 ; i< len ; i++)
    {
        long long ch = ChangeBack(s[i]);

        if(A[now][ch] == 0)
            A[now][ch] = ++tot;
        now = A[now][ch];
        Num[now]++;
    }
    End[now] = true;
    return ;
}

long long Find(char s[])
{
    long long now = 0;
    long long len = strlen(s);
    for(long long i = 0 ; i< len ; i++)
    {
        long long ch = ChangeBack(s[i]);
        if(A[now][ch] == 0)
            return 0;
        now = A[now][ch];
    }
    return Num[now];
}

void mem(void)
{
    for(int i = 1 ; i<= tot ; i++)
    {
        for(int j = 1 ; j<= 70 ; j++)
            A[i][j] = 0;
    }
    for(int i = 1 ; i<= tot ; i++)
        Num[i] = 0;
    End.reset();
    tot = 0;
    return ;
}

int main()
{
    scanf("%lld",&T);
    while(T--)
    {

        scanf("%lld%lld",&N,&Q);
        mem();
        for(long long i = 1 ; i<= N ; i++)
        {
            scanf("%s",&s);
            Insert(s);
        }
        for(long long i = 1 ; i<= Q ; i++)
        {
            scanf("%s",&s);
            printf("%lld\n",Find(s));
        }
    }
    return 0;
}

by Untitled_unrevised @ 2022-11-30 18:56:07

为什么 mem() 里面的 j 循环是到 300?


by Untitled_unrevised @ 2022-11-30 18:58:18

mem() 里面 A[i][0] 没清理到(j 从 1 开始的)


by 刘辰雨 @ 2022-11-30 19:00:23

@Untitled_unrevised

谢谢您,已A


上一页 |