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

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

#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:23:02

为什么读入字符串用的是 &s？

by Untitled_unrevised @ 2022-11-30 18:27:02

tot 看起来没有初始化

by 刘辰雨 @ 2022-11-30 18:35:46

@Untitled_unrevised

tot初始化了，mem（）里面

字符数组读入用 %s

by NightTide @ 2022-11-30 18:39:55

@刘辰雨 读入错了

by NightTide @ 2022-11-30 18:40:31

@刘辰雨

scanf("%s",s);

by Untitled_unrevised @ 2022-11-30 18:40:32

在 ChangeBack 里，字符 Z 和字符 a 输出的编码是一样的（都是 35）

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

@Hoshino_kaede 我特意去验证了一下，似乎 &s 和 s 都可以？

by NightTide @ 2022-11-30 18:42:16

@Untitled_unrevised 那我就不清楚了，s 本身出来的就是一个地址吧。

by NightTide @ 2022-11-30 18:43:23

建议学习 后缀自动机 而非字典树（逃

by 刘辰雨 @ 2022-11-30 18:45:53

@Untitled_unrevised 改了，52了

#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 10+a-'A';
    if('a' <= a && a <= 'z')
        return 36+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<= 300 ; 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;
}