Trie

Cây tiền tố

Gốc của Trie là xâu rỗng. Từ nút ứng với tiền tố $p$, cạnh mang chữ $c$ dẫn tới nút ứng với $pc$. Cạnh chỉ được tạo khi có xâu thật sự đi qua nó, nên Trie của các xâu an, and, ant, bad, be có an và and dùng chung đường a → n, rồi tách thành hai nhánh d và t.

Một nút có thể vừa là từ hoàn chỉnh vừa là tiền tố của từ khác: an là từ, đồng thời là tiền tố của and và ant. Vì vậy chỉ biết “đường đi tồn tại” thì trả lời được câu hỏi tiền tố, nhưng chưa trả lời được câu hỏi “từ $s$ đã được thêm chưa”: nếu chỉ thêm and thì đường a → n vẫn tồn tại dù an chưa từng được thêm. Mỗi nút cần thêm một trường en đánh dấu có từ kết thúc tại đây (đếm số lần nếu cho phép trùng).

Cài đặt bằng mảng. Đánh số nút $0, 1, 2, \dots$, gốc là 0. nxt[u][c] là nút con của $u$ theo chữ $c$; bằng 0 nghĩa là chưa có cạnh (gốc không là con của ai nên dùng 0 làm “trống” được). Tạo nút mới là lấy số tiếp theo ++sz.

Mỗi ký tự chèn vào tạo nhiều nhất một nút, nên số nút không vượt $1 + S$, với $S$ là tổng độ dài các xâu. Bộ nhớ là $26(S + 1)$ số nguyên: $S = 10^6$ cho khoảng 104 MB, cần kiểm với giới hạn bộ nhớ.

int nxt[N][26], sz;
bool en[N];

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
    }
    en[u] = 1;
}

Bảng chữ cái lớn hoặc thưa thì có người để mỗi nút một map. Tiết kiệm chỗ, nhưng chậm hơn thấy rõ:

Mảng nhanh gấp khoảng 4 lần. Bảng chữ cái nhỏ thì cứ dùng mảng, chỉ đổi sang map khi bộ nhớ không đủ.

Ví dụKho Từ Động

Đề. Kho từ ban đầu rỗng, $q \le 3 \cdot 10^4$ lệnh insert s, search s (đã thêm đúng từ $s$ chưa) và prefix s (có từ nào bắt đầu bằng $s$). Tổng độ dài mọi chuỗi không vượt $10^6$.

Lời giải. Trie chữ thường: nút 0 là gốc, nxt[u][c] là con của $u$ theo chữ $c$ (0 nghĩa là chưa có), en[u] bật khi có một từ kết thúc đúng tại $u$. Mỗi lệnh đi theo các ký tự của $s$.

Bước 1: thêm một từ. Đi từ gốc theo từng ký tự, cạnh nào còn thiếu thì tạo nút mới, cuối cùng bật en ở nút cuối.

int u = 0;
for (char ch : s) {
    int c = ch - 'a';
    if (!nxt[u][c]) nxt[u][c] = ++sz;
    u = nxt[u][c];
}
en[u] = 1;

Bước 2: đi theo một xâu. walk trả về nút ứng với $s$, hoặc $-1$ nếu đường đứt giữa chừng (có ký tự không có cạnh).

int walk(string s) {
    int u = 0;
    for (char ch : s) {
        u = nxt[u][ch - 'a'];
        if (!u) return -1;
    }
    return u;
}

Bước 3: hai loại câu hỏi. prefix s đúng khi đi được hết $s$: có ít nhất một từ đi qua nút đó. search s cần thêm en bật, vì đi được hết chỉ nói $s$ là tiền tố của một từ nào đó.

int u = walk(s);
bool ok = u != -1 && (op == "prefix" || en[u]);

Với ví dụ, sau insert can, search ca là NO vì ca chưa phải từ, còn prefix ca là YES.

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

const ll N = 1e6 + 5;
int nxt[N][26], sz;
bool en[N];

int walk(string s) {
    int u = 0;
    for (char ch : s) {
        u = nxt[u][ch - 'a'];
        if (!u) return -1;
    }
    return u;
}

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

    ll q;
    cin >> q;
    while (q--) {
        string op, s;
        cin >> op >> s;
        if (op == "insert") {
            int u = 0;
            for (char ch : s) {
                int c = ch - 'a';
                if (!nxt[u][c]) nxt[u][c] = ++sz;
                u = nxt[u][c];
            }
            en[u] = 1;
        } else {
            int u = walk(s);
            bool ok = u != -1 && (op == "prefix" || en[u]);
            cout << (ok ? "YES" : "NO") << '\n';
        }
    }
}

+11 dòngChạyInput10
insert can
search can
search ca
prefix ca
insert cap
prefix cat
insert ca
search ca
prefix c
search cap

OutputYES
NO
YES
NO
YES
YES
YES

Mỗi lệnh $O(|s|)$, tổng $O(10^6)$; số nút không vượt tổng độ dài các từ đã thêm.

Đếm qua nút

Trường thứ hai hay dùng là cnt[u]: số xâu đã chèn có đường đi qua nút $u$. Khi chèn, tăng cnt ở mỗi nút vừa đi tới. Khi hỏi tiền tố $p$: đường đứt thì đáp án 0, ngược lại cnt ở nút cuối là số xâu bắt đầu bằng $p$. Chèn sun, sum, s, moon, sun cho nút s có $\mathrm{cnt} = 4$, su có 3, sun có 2; từ s dừng ở nút s nên làm tăng cnt của s mà không đụng tới su.

Bất biến sau mỗi lần chèn: cnt[u] bằng đúng số xâu đã xử lý có $u$ là một tiền tố, vì chèn một xâu tăng đúng các nút trên đường của nó. Xóa một xâu là giảm cnt trên đường, với điều kiện xâu đó thật sự có mặt.

Đếm cặp. Nút ở độ sâu $d$ có cnt[u] xâu đi qua thì cả $\binom{\mathrm{cnt}}{2}$ cặp trong số đó chung ít nhất $d$ ký tự đầu. Một cặp có tiền tố chung dài $L$ đi qua cùng nhau đúng một nút ở mỗi độ sâu $1, \dots, L$, nên tổng $\binom{\mathrm{cnt}[u]}{2}$ trên mọi nút khác gốc bằng tổng độ dài tiền tố chung của mọi cặp. Cách tính tại chỗ: khi chèn một xâu mới, cộng cnt của mỗi nút nó đi qua trước khi tăng, tức là cộng số xâu cũ còn chung tiền tố tới độ sâu đó.

Ví dụTổng Độ Dài Tiền Tố Chung

Đề. Cho $N$ xâu (tổng độ dài không quá $3 \cdot 10^5$). In tổng độ dài tiền tố chung dài nhất của mọi cặp vị trí $i < j$.

Lời giải. Đúng phép đếm cặp ở trên: chèn lần lượt từng xâu, ở mỗi ký tự cộng cnt của nút vừa tới (số xâu cũ đã đi qua nút đó) rồi mới tăng nó. Mỗi cặp $(i, j)$ với $i < j$ được cộng đúng một lần ở mỗi độ sâu chung, lúc chèn xâu $j$. Hai xâu trùng nội dung vẫn là hai vị trí, và cách đếm tự xử lý đúng. Đáp án tới cỡ $\binom{3 \cdot 10^5}{2}$, phải ll. Với ví dụ, cặp (sun, sun) góp 3, (sun, sum) góp 2 hai lần, mỗi cặp có s góp 1: tổng 10.

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

const ll N = 3e5 + 5;
int nxt[N][26], sz;
ll cnt[N];

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

    ll n, ans = 0;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!nxt[u][c]) nxt[u][c] = ++sz;
            u = nxt[u][c];
            ans += cnt[u];
            cnt[u]++;
        }
    }
    cout << ans << '\n';
}

ChạyInput5
sun
sum
s
moon
sun

Output10

XOR lớn nhất

Trie không bắt buộc là cây trên chữ cái. Viết mỗi số không âm bằng đúng $B$ bit (thêm số 0 ở đầu cho đủ), từ bit cao xuống bit thấp, rồi chèn như một xâu trên bảng chữ cái $\{0, 1\}$. Đây là Trie nhị phân: mỗi nút có hai con, độ sâu đúng $B$, và mỗi số là một đường từ gốc tới lá.

Muốn tìm $\max_y (x \oplus y)$ trên các số $y$ trong Trie, đi từ gốc và quyết định từng bit từ cao xuống: ở bit $b$, nếu có nhánh mang bit ngược với bit $b$ của $x$ thì đi nhánh đó, kết quả nhận bit 1; không có thì đành đi nhánh cùng bit. Tham lam này đúng vì bit $2^b$ lớn hơn tổng mọi bit thấp, $2^{b-1} + \dots + 1 = 2^b - 1$: một kết quả có bit $b$ bằng 1 luôn lớn hơn mọi kết quả có bit $b$ bằng 0 và cùng các bit cao hơn (bài 14). Mỗi truy vấn đúng $B$ bước, với số dưới $2^{31}$ là 31 bước.

Ví dụCặp XOR Lớn Nhất

Đề. Cho $n \le 2 \cdot 10^5$ số $a_i < 2^{31}$. In $\max a_i \oplus a_j$ trên mọi cặp $i \le j$.

Lời giải. Duyệt mọi cặp là $2 \cdot 10^{10}$. Chèn các số vào Trie nhị phân theo 31 bit, từ bit cao xuống bit thấp; với mỗi $a_i$, đi tham lam như trên để tìm $\max_j a_i \oplus a_j$, rồi lấy lớn nhất. Có thể chèn tất cả trước rồi mới hỏi, vì cặp $i = j$ chỉ cho 0, không làm sai cực đại. Với ví dụ, $5 \oplus 25 = 7 \oplus 25 = 30$ là lớn nhất.

Bước 1: chèn một số. Đi từ bit 30 xuống bit 0, mỗi bit là một cạnh 0 hoặc 1.

void insert(ll x) {
    int u = 0;
    for (ll b = 30; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
    }
}

Bước 2: XOR lớn nhất với $x$. Ở mỗi bit, muốn bit tương ứng của kết quả bằng 1 thì phải đi sang nhánh ngược bit của $x$; nhánh đó có thì đi và bật bit $b$ của kết quả, không có thì đành đi nhánh cùng bit. Tham lam đúng vì bit cao quyết định trước: $2^b$ lớn hơn tổng mọi bit thấp hơn.

ll query(ll x) {
    int u = 0;
    ll res = 0;
    for (ll b = 30; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (nxt[u][c ^ 1]) {
            res |= 1LL << b;
            u = nxt[u][c ^ 1];
        } else u = nxt[u][c];
    }
    return res;
}

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

const ll N = 2e5 * 31 + 5;
int nxt[N][2], sz;
ll n, a[200005];

void insert(ll x) {
    int u = 0;
    for (ll b = 30; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
    }
}

ll query(ll x) {
    int u = 0;
    ll res = 0;
    for (ll b = 30; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (nxt[u][c ^ 1]) {
            res |= 1LL << b;
            u = nxt[u][c ^ 1];
        } else u = nxt[u][c];
    }
    return res;
}

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

    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++) ans = max(ans, query(a[i]));
    cout << ans << '\n';
}

ChạyInput5
7 2 12 25 10

Output30

$O(31n)$ thời gian; số nút tối đa $31n + 1 \approx 6{,}2 \cdot 10^6$, mỗi nút hai số int, khoảng 50 MB.

Cùng ý tưởng giải bài “XOR lớn nhất của một đoạn con”: XOR đoạn $[l, r]$ là $P_r \oplus P_{l-1}$ với $P$ là XOR tiền tố (bài 02), nên chèn dần các $P$ vào Trie, mỗi $P_r$ hỏi XOR lớn nhất với các $P$ đã có rồi mới chèn.

Xóa và đếm

Để Trie nhị phân chứa một đa tập thay đổi được, giữ cnt[u] là số phần tử hiện có đi qua nút $u$. Thêm là tăng cnt trên đường, xóa một bản sao là giảm. Nút có thể đã tồn tại nhưng cnt bằng 0 khi mọi phần tử của nó đã bị xóa; lúc đi tham lam phải hỏi “nhánh này còn phần tử không” bằng cnt > 0, không phải “cạnh này đã từng được tạo chưa”. Quên điều đó là lỗi khó thấy nhất: chương trình chọn một giá trị đã xóa và in ra một XOR không tồn tại.

Đếm $y$ có $x \oplus y < l$. Đi theo bit từ cao xuống, giữ nút $u$ là tập các $y$ mà $x \oplus y$ trùng với $l$ ở mọi bit cao hơn đã xét. Ở bit $b$, gọi $c$ là bit $b$ của $x$. Nếu bit $b$ của $l$ bằng 1 thì mọi $y$ trong nhánh $c$ cho $x \oplus y$ có bit $b$ bằng 0, nhỏ hơn $l$ chắc chắn: cộng cả cnt của nhánh $c$, rồi đi tiếp nhánh $c \oplus 1$ để giữ bằng $l$. Nếu bit $b$ của $l$ bằng 0 thì phải đi nhánh $c$ (nhánh kia làm $x \oplus y$ vượt $l$). Hết bit thì $x \oplus y = l$, không tính vì bất đẳng thức chặt. Đây đúng là cách đếm theo vị trí rẽ nhánh của quy hoạch động chữ số (bài 13), chạy trên cây.

Ví dụĐếm XOR Dưới Ngưỡng

Đề. Đa tập ban đầu rỗng, $q \le 10^5$ sự kiện: 1 p thêm $p$, 2 p xóa một bản sao của $p$, 3 p l in số bản sao $x$ có $(x \oplus p) < l$. Mọi giá trị không quá $10^8 < 2^{27}$.

Lời giải. Trie nhị phân 27 bit, mỗi nút giữ cnt như đã nói ở trên. Đếm số $x$ có $x \oplus p < l$ bằng cách đi theo các bit của $l$ từ cao xuống. Ở bit $b$, mọi $x$ trong nút hiện tại đã có $x \oplus p$ trùng với $l$ ở các bit cao hơn.

• Bit $b$ của $l$ bằng 1: các $x$ có bit $b$ cùng bit của $p$ cho $x \oplus p$ bằng 0 ở bit này, nhỏ hơn $l$ ngay, nên cộng cả cnt của nhánh đó; rồi đi sang nhánh ngược bit để tiếp tục trùng với $l$.
• Bit $b$ của $l$ bằng 0: chỉ nhánh cùng bit giữ được $x \oplus p$ trùng với $l$; nhánh ngược bit cho bit 1, lớn hơn $l$, bỏ.

Đi hết 27 bit mà vẫn trùng thì $x \oplus p = l$, không tính. Gặp nhánh chưa tồn tại thì dừng sớm. Với ví dụ, đa tập $\{5, 2, 5\}$ và $p = 4$, $l = 4$: $5 \oplus 4 = 1 < 4$ hai lần, $2 \oplus 4 = 6$ thì không, đáp án 2.

Bước 1: thêm, xóa. add(x, d) cộng $d$ ($+1$ hoặc $-1$) vào cnt trên đường của $x$, tạo nút khi cần.

void add(ll x, int d) {
    int u = 0;
    for (ll b = 26; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
        cnt[u] += d;
    }
}

Bước 2: đếm theo các bit của $l$.

ll calc(ll p, ll l) {
    int u = 0;
    ll res = 0;
    for (ll b = 26; b >= 0; b--) {
        int c = (p >> b) & 1;
        if ((l >> b) & 1) {
            if (nxt[u][c]) res += cnt[nxt[u][c]];
            u = nxt[u][c ^ 1];
        } else u = nxt[u][c];
        if (!u) break;
    }
    return res;
}

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

const ll N = 1e5 * 27 + 5;
int nxt[N][2], cnt[N], sz;

void add(ll x, int d) {
    int u = 0;
    for (ll b = 26; b >= 0; b--) {
        int c = (x >> b) & 1;
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
        cnt[u] += d;
    }
}

ll calc(ll p, ll l) {
    int u = 0;
    ll res = 0;
    for (ll b = 26; b >= 0; b--) {
        int c = (p >> b) & 1;
        if ((l >> b) & 1) {
            if (nxt[u][c]) res += cnt[nxt[u][c]];
            u = nxt[u][c ^ 1];
        } else u = nxt[u][c];
        if (!u) break;
    }
    return res;
}

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

    ll q;
    cin >> q;
    while (q--) {
        ll t, p;
        cin >> t >> p;
        if (t == 1) add(p, 1);
        else if (t == 2) add(p, -1);
        else {
            ll l;
            cin >> l;
            cout << calc(p, l) << '\n';
        }
    }
}

ChạyInput8
1 5
1 2
1 5
3 4 4
2 5
3 4 4
3 7 3
2 5

Output2
1
1

Mỗi sự kiện 27 bước.

Cắt xâu bằng Trie

Một bài quen: đếm số cách cắt xâu $s$ thành các từ của một từ điển. Gọi $\mathrm{dp}_i$ là số cách ghép đúng $i$ ký tự đầu của $s$, $\mathrm{dp}_0 = 1$. Từ vị trí $i$, mọi từ $w$ khớp với $s$ bắt đầu tại $i$ cho một bước chuyển $\mathrm{dp}_{i + |w|} \mathrel{+}= \mathrm{dp}_i$. Thử từng từ của từ điển ở mỗi vị trí là $|s| \cdot k$ phép so xâu, quá chậm khi $k = 10^5$.

Trie liệt kê đúng những từ khớp tại $i$ mà không thử từ nào thừa: đi xuống Trie theo $s_i, s_{i+1}, \dots$, mỗi lần tới một nút có en bật là gặp một từ kết thúc ở vị trí ấy, và dừng ngay khi đường đứt. Mỗi vị trí đi xuống tối đa độ dài từ dài nhất $L$ bước, tổng $O(|s| \cdot L)$, không phụ thuộc số từ. Cùng khuôn ấy dùng cho bài cắt xâu ít đoạn nhất, hay giải mã một xâu đã ghép từ các từ (truy vết dp để in các từ).

Ví dụGhép Chuỗi Từ Từ Điển

Đề. Cho xâu $s$ ($|s| \le 5000$) và $k \le 10^5$ từ đôi một khác nhau (tổng độ dài $10^6$). Đếm số cách viết $s$ thành phép nối các từ (mỗi từ dùng bao nhiêu lần cũng được), theo modulo $10^9 + 7$.

Lời giải. $\mathrm{dp}_i$ là số cách viết $i$ ký tự đầu của $s$ thành phép nối các từ, $\mathrm{dp}_0 = 1$. Từ vị trí $i$, đi xuống Trie theo $s_i, s_{i+1}, \dots$; mỗi nút có en bật tại ký tự $j$ là một từ khớp đúng đoạn $s[i..j]$, nên cộng $\mathrm{dp}_i$ vào $\mathrm{dp}_{j+1}$. Trie cho mọi từ bắt đầu tại $i$ trong một lượt đi, thay vì so từng từ. Với ví dụ aaaa và từ điển a, aa, aaa: có 7 cách, chính là số cách viết 4 thành tổng có thứ tự các số 1, 2, 3.

Bước 1: dựng Trie các từ.

while (k--) {
    string w;
    cin >> w;
    int u = 0;
    for (char ch : w) {
        int c = ch - 'a';
        if (!nxt[u][c]) nxt[u][c] = ++sz;
        u = nxt[u][c];
    }
    en[u] = 1;
}

Bước 2: quy hoạch động đẩy tới. Chỉ đẩy từ các $\mathrm{dp}_i$ khác 0; đường đứt (không còn từ nào có tiền tố này) thì dừng sớm.

dp[0] = 1;
for (ll i = 0; i < n; i++) {
    if (!dp[i]) continue;
    int u = 0;
    for (ll j = i; j < n; j++) {
        u = nxt[u][s[j] - 'a'];
        if (!u) break;
        if (en[u]) dp[j + 1] = (dp[j + 1] + dp[i]) % MOD;
    }
}

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

const ll N = 1e6 + 5, MOD = 1e9 + 7;
int nxt[N][26], sz;
bool en[N];
ll dp[5005];

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

    string s;
    ll k;
    cin >> s >> k;
    while (k--) {
        string w;
        cin >> w;
        int u = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[u][c]) nxt[u][c] = ++sz;
            u = nxt[u][c];
        }
        en[u] = 1;
    }
    ll n = s.size();
    dp[0] = 1;
    for (ll i = 0; i < n; i++) {
        if (!dp[i]) continue;
        int u = 0;
        for (ll j = i; j < n; j++) {
            u = nxt[u][s[j] - 'a'];
            if (!u) break;
            if (en[u]) dp[j + 1] = (dp[j + 1] + dp[i]) % MOD;
        }
    }
    cout << dp[n] << '\n';
}

ChạyInputaaaa
3
a
aa
aaa

Output7

Mỗi vị trí đi xuống tối đa $|s|$ bước, tổng $|s|^2 / 2 \approx 1{,}25 \cdot 10^7$ trong trường hợp xấu; dựng Trie $O(10^6)$.