#2#3#4#5TLE,请求各位帮助,谢谢!

P8306 【模板】字典树

smartbrisk @ 2024-08-07 08:19:43

模板题,#2#3#4#5都是TLE,但答案我下载下来发现都是对的,请求各位帮助,谢谢!

#include <cstdio>
#include <cstring>
#include <cstdlib>

const int N = 3e6 + 10;
int pass[N], nexts[N][62], numNode = 1;
char str[N];

inline int charToInt(char ch)
{
    return ch >= '0' && ch <= '9' ? ch - '0' :
     (ch >= 'A' && ch <= 'Z' ? 10 + ch - 'A' : 36 + ch - 'a');
}

void addStr()
{
    int node = 0, len = strlen(str);
    for (int i = 0; i < len; ++i)
    {
        if (nexts[node][charToInt(str[i])] == -1)
        {
            nexts[node][charToInt(str[i])] = numNode++;
        }
        node = nexts[node][charToInt(str[i])];
        ++pass[node];
    }
}

int query()
{
    int node = 0, len = strlen(str);
    for (int i = 0; i < len; ++i)
    {
        if (nexts[node][charToInt(str[i])] == -1)
        {
            return 0;
        }
        node = nexts[node][charToInt(str[i])];
    }    
    return pass[node];
}

int main()
{
    // freopen("trie.in", "r", stdin);
    // freopen("trie.out", "w", stdout);
    int T, n, q;
    scanf("%d", &T);
    while (T--)
    {
        memset(nexts, -1, sizeof(nexts));
        memset(pass, 0, sizeof(pass));
        numNode = 1;
        scanf("%d%d", &n, &q);
        while (n--)
        {
            scanf("%s", str);
            addStr();
        }
        while (q--)
        {
            scanf("%s", str);
            printf("%d\n", query());
        }
    }
    //system("pause");
}

我把字符转化为数字的方法是:把'0''9' 对应到 09\ 把 'A''Z' 对应到 1035\ 把 'a''z' 对应到 3661


by _chicken_ @ 2024-08-07 10:15:00

@smartbrisk

TLE是因为memset超时了 改成for循环清空就行(应该


by smartbrisk @ 2024-08-07 10:46:54

我改对了,谢谢!


|