指针trie wa 2 3 4

P8306 【模板】字典树

Tibrella @ 2023-02-24 21:31:50

我又来求助了...
思路是每次加字符串的时候把经过的每个点权值加一
模板题都打不明白属于是太弱了

#include <array>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>

#define MAX 3000005

struct Node {
    std::array<Node*, '{' - '0' + 1> son;
    int cnt;
    int siz;
} trie[MAX];

using std::string;

Node* idx = trie;

void insert(string& s) {
    Node* pos = trie;
    for (auto c : s) {
        if (!pos->son[c - '0']) pos->son[c - '0'] = ++idx;
        ++ (pos->siz);
        pos = pos->son[c - '0'];
    }
    ++(pos->cnt);
    ++pos->siz;
}

// void dfs(Node* nod) {
//     nod->siz = nod->cnt;
//     for (auto i : nod->son) {
//         if (!i) continue;
//         dfs(i);
//         nod->siz += i->siz;
//     }
//     // std::cout << nod->cnt << ' ' << nod->siz << std::endl;
// }

int query(string& s) {
    Node* pos = trie;
    for (auto c : s) {
        if (!pos->son[c - '0']) {
            return 0;
        }
        pos = pos->son[c - '0'];
    }
    return pos->siz;
}

using std::cin;
using std::cout;

#define endl '\n'

int n, q;
string str;
int t;

// #define cin fin
// #define cout fout

int main() {
    // std::ifstream fin("1.in", std::ios::in);
    // std::ofstream fout("1.out", std::ios::out);

    std::ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;

    while (t--) {
        cin >> n >> q;
        ++idx;
        for (; idx != trie; --idx) {
            idx->cnt = idx->siz = 0;
            idx->son.fill(0);
        }
        idx = trie;

        while (n--) {
            cin >> str;
            insert(str);
        }
        // dfs(trie);
        // for (Node* nod = trie; nod != idx + 1; ++nod) {
        //     nod->siz += nod->cnt;
        // }

        while (q--) {
            cin >> str;
            cout << query(str) << endl;
        }
    }

    return 0;
}

by cjwdxfblzs @ 2023-02-25 20:25:38

指针带师 拜谢!!!


|