36分求调

P8306 【模板】字典树

__Floze3__ @ 2023-08-23 21:21:57

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

int trie[3000005][65], T, n, q, idx, cnt[3000005];

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

void insert(string s){
    int p = 0, l = s.size();
    for (int i = 0; i < l; i++){
        int q = getsum(s[i]);
        if (!trie[p][q]) trie[p][q] = ++idx;
        p = trie[p][q];
        cnt[p]++;
    }
    return ;
}

int find(string s){
    int p = 0, l = s.size();
    for (int i = 0; i < l; i++){
        int q = getsum(s[i]);
        if (!trie[p][q]) return 0;
        p = trie[p][q];
    } 
    return cnt[p];
}

int main(){
    cin >> T;
    while(T--){
        for (int i = 0; i <= idx + 10; i++){
            for (int j = 0; j < 64; j++){
                trie[i][j] = 0;
            }
        }
        for (int i = 0; i <= idx; i++) cnt[i] = 0;
        idx = 0;
        cin >> n >> q;
        for (int i = 0; i < n; i++){
            string s;
            cin >> s;
            insert(s);
        }
        for (int i = 0; i < q; i++){
            string s;
            cin >> s;
            cout << find(s) << endl;
        }
    }
    return 0;
} 

by Ifyoung @ 2023-08-23 21:31:43

getsum 函数中 else if 那一行后面少了 return


by Ifyoung @ 2023-08-23 21:32:52

还有就是主函数中 while (T -- ) 的下一行 idx + 10 是什么意思?为什么要 + 10


by Ifyoung @ 2023-08-23 21:32:57

@Floze3


|