蜜汁RE,有人帮忙看看吗?

P8306 【模板】字典树

Link_Cut_Y @ 2022-10-06 21:10:25

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1000010;
char str[N];
int idx, n, m, T, cnt; 
unordered_map<char, int> Map;
struct Trie {
    int s[70], val;
    void clear() {
        memset(s, 0, sizeof s);
        val = 0;
    }
}tr[N];

int id(char x) { return Map[x]; }
void clear() {
    for (int i = 0; i <= idx; i ++ )
        tr[i].clear();
    idx = 0;
}

void insert(char *str, int len) {
    int u = 0;
    for (int i = 0; i < len; i ++ ) {
        int v = id(str[i]);
        if (!tr[u].s[v]) tr[u].s[v] = ++ idx;
        u = tr[u].s[v];
    }
    tr[u].val ++ ;
}

void dfs(int u) {
    for (int i = 0; i < cnt; i ++ )
        if (tr[u].s[i]) {
            dfs(tr[u].s[i]);
            tr[u].val += tr[tr[u].s[i]].val;
        }
}

int query(char *str, int len) {
    int u = 0;
    for (int i = 0; i < len; i ++ ) {
        int v = id(str[i]);
        if (!tr[u].s[v]) return 0;
        u = tr[u].s[v];
    }
    return tr[u].val;
}

void init() {
    for (char i = '0'; i <= '9'; i ++ ) Map[i] = cnt ++ ;
    for (char i = 'a'; i <= 'z'; i ++ ) Map[i] = cnt ++ ;
    for (char i = 'A'; i <= 'Z'; i ++ ) Map[i] = cnt ++ ;
}

int main() {
//  freopen("data.in", "r", stdin);
//  freopen("my.out", "w", stdout);

    scanf("%d", &T);
    init();
    while (T -- ) {
        clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
            scanf("%s", str), insert(str, strlen(str));
        dfs(0);
        while (m -- ) {
            scanf("%s", str);
            printf("%d\n", query(str, strlen(str)));
        }
    }
    return 0;
}

by _cyh0412_ @ 2022-10-06 21:12:57

数组小不小


by Link_Cut_Y @ 2022-10-06 21:13:48

@cyh0412 找到锅了,3 \times 10 ^ 6 开成 1 \times 10 ^ 6 了,此贴终结。


by _cyh0412_ @ 2022-10-06 21:19:10

@Mount_

是不是给个关注啥的


by Link_Cut_Y @ 2022-10-06 21:57:41

@cyh0412 已经关注了,互关吧


by _cyh0412_ @ 2022-10-06 22:06:00

@Mount_ 关了


|