Trie WA 求助

P8306 【模板】字典树

huangrenheluogu @ 2023-11-21 21:11:48

Wa on #2, #3,#4

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, M = 63;
int T, n, q, nxt[N * M][M], cnt, fin[N * M], len, x, p;
string s;
inline void init(){
    for(int i = 0; i <= cnt; i++){
        fin[i] = 0;
        for(int j = 1; j <= 62; j++) nxt[i][j] = 0;
    }
    cnt = 0;
}
inline int work(char c){
    if('a' <= c && c <= 'z') return c - 'a' + 1;
    if('A' <= c && c <= 'Z') return c - 'A' + 27;
    return c - '0' + 53;
}
inline void upd(){
    p = 0;
    for(int i = 0; i < len; i++){
        x = work(s[i]);
        if(!nxt[p][x]) nxt[p][x] = ++cnt;
        p = nxt[p][x];
        fin[p]++;
    }
}
inline int query(){
    int res = 0;
    p = 0;
    for(int i = 0; i < len; i++){
        x = work(s[i]);
        if(!nxt[p][x]) return 0;
        p = nxt[p][x];
    }
    return fin[p];
}
int main(){
    scanf("%d", &T);
    while(T--){
        init();
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++){
            cin >> s;
            len = s.size();
            upd();
        }
        for(int i = 1; i <= q; i++){
            cin >> s;
            len = s.size();
            printf("%d\n", query());
        }
    }
    return 0;
}

by LittleChara @ 2023-11-21 21:35:33

@huangrenheluogu 数组越界,trie 第一维得开字符串总长度。


by huangrenheluogu @ 2023-11-22 06:47:16

@一只小chara 谢谢。


|