救救我,字典树18分

P8306 【模板】字典树

BartAllen @ 2023-01-31 18:38:44

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 5;

int t, q, n, tot = 1;
int trie[N][65], cnt[N];
string s;

int getint(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a' + 26;
    if (c >= 'A' && c <= 'Z') return c - 'A';
    if (c >= '0' && c <= '9') return c - '0' + 52;
}

void insert(string str) {
    int len = str.size(), p = 1;
    for (int k = 0; k < len; k++) {
        int ch = getint(str[k]);
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
        cnt[p]++;
    }
}

int search(string str) {
    int len = str.size(), p = 1;
    for (int k = 0; k < len; k++) {
        p = trie[p][getint(str[k])];
        if (!p) return 0;
    }
    return cnt[p];
}

int main() {
    int i, j;
    scanf("%d", &t);
    while (t--) {
        for (i = 1; i <= tot; i++)
            for (j = 1; j <= 130; j++) trie[i][j] = 0;
        for (i = 1; i <= tot; i++) cnt[i] = 0;
        tot = 0;
        scanf("%d%d", &n, &q);
        for (i = 1; i <= n; i++) {
            cin >> s;
            insert(s);
        }
        for (i = 1; i <= q; i++) {
            cin >> s;
            printf("%d\n", search(s));
        }
    }
    return 0;
}

by syta @ 2023-01-31 18:47:36

数组是不是越界了啊(


by BartAllen @ 2023-01-31 18:54:33

@syta 谢谢大佬,我写代码太不仔细了


by syta @ 2023-01-31 18:54:54

@BarryAllen_4

for (j = 1; j <= 130; j++) trie[i][j] = 0;

一个是数组越界

tot = 0;

另一个是这个应该为=1


|