Cây tiền tố (Trie)

Mức độ: Chuyên sâu

Có 10⁵ từ trong từ điển và 10⁵ câu hỏi “có bao nhiêu từ bắt đầu bằng ba?”. Đi qua cả từ điển cho mỗi câu hỏi thì quá chậm. Trie (cây tiền tố) xếp các từ vào một cây mà mỗi cạnh là một ký tự: các từ có chung tiền tố thì đi chung đường. Câu hỏi về tiền tố p chỉ cần đi |p| bước từ gốc.

Cấu trúc

Mỗi nút ứng với một tiền tố. Gốc là tiền tố rỗng; nút con theo cạnh c của nút ứng với tiền tố x là nút ứng với tiền tố x + c. Mỗi nút lưu thêm: qua[u] là số từ đi qua nút (số từ có tiền tố đó) và het[u] là số từ kết thúc đúng ở nút.

Trie của các từ ban, bang, bao, ca:

(gốc)
 ├─ b ── a ─┬─ n (het 1) ── g (het 1)
 │          └─ o (het 1)
 └─ c ── a (het 1)

Số từ bắt đầu bằng ba là qua[nút “ba”] = 3.

Python

import sys
du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
con = [{}]            # con[u]: từ điển ký tự -> nút con
qua = [0]
for tu in du_lieu[2:2 + n]:
    u = 0
    qua[0] += 1
    for c in tu:
        if c not in con[u]:
            con[u][c] = len(con)
            con.append({})
            qua.append(0)
        u = con[u][c]
        qua[u] += 1
ket_qua = []
for p in du_lieu[2 + n:2 + n + q]:
    u = 0
    for c in p:
        u = con[u].get(c, -1)
        if u < 0:
            break
    ket_qua.append(qua[u] if u >= 0 else 0)
print("\n".join(map(str, ket_qua)))

C++

#include <iostream>
#include <string>
#include <vector>
#include <array>
using namespace std;

vector<array<int, 26>> con;    // con[u][c]: nút con theo ký tự c, -1 nếu chưa có
vector<int> qua;

int taoNut() {
    array<int, 26> rong;
    rong.fill(-1);
    con.push_back(rong);
    qua.push_back(0);
    return con.size() - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    taoNut();
    for (int i = 0; i < n; i++) {
        string tu;
        cin >> tu;
        int u = 0;
        qua[0]++;
        for (char ch : tu) {
            int c = ch - 'a';
            if (con[u][c] < 0) {
                int moi = taoNut();
                con[u][c] = moi;
            }
            u = con[u][c];
            qua[u]++;
        }
    }
    while (q--) {
        string p;
        cin >> p;
        int u = 0;
        for (char ch : p) {
            u = con[u][ch - 'a'];
            if (u < 0) break;
        }
        cout << (u >= 0 ? qua[u] : 0) << "\n";
    }
    return 0;
}

Thêm một từ mất |từ| bước, mỗi câu hỏi mất |p| bước. Bộ nhớ tỉ lệ với tổng độ dài các từ.

Lưu ý: trong C++, gán con[u][c] = taoNut() có thể lỗi vì taoNut thêm phần tử làm con cấp phát lại bộ nhớ trong lúc đang dùng con[u]. Lưu kết quả vào biến trước rồi mới gán, như chương trình trên.

Trie nhị phân và XOR

Với các số, viết mỗi số thành dãy bit từ bit cao xuống bit thấp và cho vào Trie (mỗi nút có hai con 0 và 1). Câu hỏi “số nào trong tập cho XOR lớn nhất với x?” trả lời tham lam từ bit cao: ở mỗi bit, nếu có nhánh với bit ngược bit của x thì đi nhánh đó (bit này của kết quả bằng 1), không thì đi nhánh còn lại.

Tham lam đúng vì bit cao hơn đáng giá hơn tổng mọi bit thấp: 2^k lớn hơn 2^{k - 1} + … + 1.

Luyện tập

Gồm 12 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Trie các từ

Bài 1. Đếm từ có tiền tố

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), n dòng sau mỗi dòng là một từ trong từ điển, q dòng sau mỗi dòng là một tiền tố p (chữ cái thường, tổng độ dài mọi xâu không quá 10⁶, các từ có thể trùng nhau). Với mỗi p, in ra số từ trong từ điển bắt đầu bằng p.

Ví dụ:

Nhập	In ra
4 3 ban bang bao ca ba bang c	3 1 1

Kiểm tra: nhập

6 4
toan
toantin
tin
tinhoc
toan
tri
to
t
tin
toantinhoc

Xem đáp số

3
6
2
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Có trong từ điển không

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), n dòng sau là các từ của từ điển, q dòng sau mỗi dòng là một từ cần tra (chữ cái thường, tổng độ dài không quá 10⁶). Với mỗi từ cần tra, in ra YES nếu nó có trong từ điển, ngược lại NO.

Ví dụ:

Nhập	In ra
4 3 ban bang bao ca ba bang cb	NO YES NO

Kiểm tra: nhập

5 4
toan
toantin
tin
tinhoc
tri
toan
tinh
tri
toantinhoc

Xem đáp số

YES
NO
YES
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Số tiền tố khác nhau

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau là các từ (chữ cái thường, tổng độ dài không quá 10⁶). In ra số xâu khác rỗng khác nhau là tiền tố của ít nhất một từ.

Ví dụ:

Nhập	In ra
4 ban bang bao ca	7

Kiểm tra: nhập

6
toan
toantin
tin
tinhoc
toan
tri

Xem đáp số

14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Danh bạ không nhầm số

Danh bạ có n số điện thoại (xâu chữ số, có thể có số trùng). Khi bấm một số, tổng đài gọi ngay khi dãy đã bấm khớp với một số trong danh bạ. Danh bạ hợp lệ khi không có số nào là tiền tố của một số khác (hai số trùng nhau cũng không hợp lệ). Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau là các số (dài từ 1 đến 10). In ra YES nếu hợp lệ, ngược lại NO.

Ví dụ:

Nhập	In ra
3 911 97625999 91125426	NO

Kiểm tra: nhập

4
113
12340
123440
12345

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Tiền tố chung dài nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau là các từ (chữ cái thường, tổng độ dài không quá 10⁶). In ra tiền tố chung dài nhất của mọi từ, hoặc - nếu tiền tố đó rỗng.

Ví dụ:

Nhập	In ra
3 flower flow flight	fl

Kiểm tra: nhập

4
toantin
toantinhoc
toan
toanhoc

Xem đáp số

toan

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Gõ phím tự hoàn thành

Từ điển có n từ khác nhau. Khi gõ một từ, máy tự hoàn thành ngay khi phần đã gõ là tiền tố của đúng một từ trong từ điển (khi đó không phải gõ tiếp); nếu tới hết từ mà vẫn chưa duy nhất thì phải gõ cả từ. Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau là các từ (chữ cái thường, khác nhau, tổng độ dài không quá 10⁶). In ra tổng số phím phải gõ để lần lượt gõ mọi từ.

Ví dụ:

Nhập	In ra
4 ban bang bao ca	11

Kiểm tra: nhập

5
toan
toantin
tin
tinhoc
tri

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Trie nhị phân

Bài 7. Cặp số có XOR lớn nhất

Dòng đầu có n (2 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰). In ra giá trị lớn nhất của a_i XOR a_j với i khác j.

Ví dụ:

Nhập	In ra
4 3 10 5 25	28

Kiểm tra: nhập

8
14 70 53 83 49 91 36 80

Xem đáp số

127

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đoạn con XOR lớn nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰). In ra giá trị XOR lớn nhất của một đoạn liên tiếp khác rỗng.

Ví dụ:

Nhập	In ra
4 1 2 3 4	7

Kiểm tra: nhập

6
8 1 2 12 7 6

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hỏi XOR lớn nhất với x

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰), q dòng sau mỗi dòng có một số x (0 ≤ x nhỏ hơn 2³⁰). Với mỗi x, in ra giá trị lớn nhất của x XOR a_i.

Ví dụ:

Nhập	In ra
4 3 3 10 5 25 6 20 0	31 30 25

Kiểm tra: nhập

6 4
14 70 53 83 49 91
100
1
63
127

Xem đáp số

106
90
121
113

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Thêm, xóa và hỏi XOR

Một túi số ban đầu chỉ có số 0. Dòng đầu có q (1 ≤ q ≤ 2 × 10⁵), q dòng sau mỗi dòng là + x (thêm x), - x (xóa một số x, chắc chắn đang có trong túi) hoặc ? x (hỏi giá trị lớn nhất của x XOR y với y trong túi), với 0 ≤ x nhỏ hơn 2³⁰. In ra đáp số các câu hỏi.

Ví dụ:

Nhập	In ra
7 + 8 + 9 + 11 + 6 + 1 ? 3 - 8	11

Kiểm tra: nhập

8
+ 5
? 2
+ 12
? 2
- 5
? 2
- 12
? 2

Xem đáp số

7
14
14
2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đếm cặp có XOR nhỏ hơn k

Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 0 ≤ k nhỏ hơn 2³⁰), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰). In ra số cặp i đứng trước j mà a_i XOR a_j nhỏ hơn k.

Ví dụ:

Nhập	In ra
4 6 1 2 3 7	5

Kiểm tra: nhập

8 10
14 7 53 8 49 1 36 0

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Trie và quy hoạch động

Bài 12. Tách xâu thành các từ

Dòng đầu là xâu s (chữ cái thường, 1 ≤ |s| ≤ 5000), dòng thứ hai có n (1 ≤ n ≤ 10⁵), n dòng sau là các từ của từ điển (khác nhau, tổng độ dài không quá 10⁶). In ra số cách tách s thành các đoạn liên tiếp mà mỗi đoạn là một từ trong từ điển, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
ababc 4 ab abab c cb	2

Kiểm tra: nhập

bumbiiacademy
6
bum
bumbii
bii
aca
academy
demy

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.