Hướng giải của Từ điển bằng Trie

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Từ điển Trie - Thêm, Tìm, Đếm tiền tố

Phân tích

Xây dựng cây Trie với mỗi node có:

child[26]: mảng con trỏ tới 26 node con (cho 26 chữ cái)
cnt: số xâu đi qua node này (dùng cho truy vấn đếm tiền tố)
end: đánh dấu xâu kết thúc tại node này

Độ phức tạp

Thời gian: O(tổng độ dài các xâu) cho mỗi thao tác
Không gian: O(tổng độ dài × 26)

Code mẫu C++

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

// Cau truc node trong cay Trie
struct TrieNode {
    TrieNode* child[26];
    int cnt;    // So xau di qua node nay
    bool end;   // Co xau ket thuc tai day khong
    TrieNode() : cnt(0), end(false) {
        // Khoi tao cac con tro la null
        fill(child, child + 26, nullptr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    TrieNode* root = new TrieNode();  // Node goc

    while (n--) {
        int t;
        string s;
        cin >> t >> s;

        if (t == 1) {
            // Them xau s vao tu dien
            TrieNode* cur = root;
            for (char c : s) {
                int idx = c - 'a';  // Chuyen ky tu thanh chi so 0-25
                if (!cur->child[idx]) {
                    cur->child[idx] = new TrieNode();  // Tao node moi neu chua co
                }
                cur = cur->child[idx];
                cur->cnt++;  // Tang so xau di qua
            }
            cur->end = true;  // Danh dau ket thuc xau
        } else if (t == 2) {
            // Hoi xau s co trong tu dien khong
            TrieNode* cur = root;
            bool found = true;
            for (char c : s) {
                int idx = c - 'a';
                if (!cur->child[idx]) {
                    found = false;
                    break;
                }
                cur = cur->child[idx];
            }
            cout << (found && cur->end ? "YES" : "NO") << endl;
        } else {
            // Dem so xau co tien to s
            TrieNode* cur = root;
            bool ok = true;
            for (char c : s) {
                int idx = c - 'a';
                if (!cur->child[idx]) {
                    ok = false;
                    break;
                }
                cur = cur->child[idx];
            }
            cout << (ok ? cur->cnt : 0) << endl;
        }
    }
    return 0;
}

Giải thích

cnt đếm số xâu đi qua node, nên truy vấn tiền tố chỉ cần duyệt tới node đó và đọc cnt.
end phân biệt giữa "xâu là tiền tố của xâu khác" và "xâu chính nó tồn tại trong từ điển".
Vì tổng độ dài tối đa \(10^5\), tổng số node tạo ra không quá \(10^5 \times 26 = 2.6 \times 10^6\), đủ với bộ nhớ 256 MB.

Nhận xét

Không có ý kiến tại thời điểm này.