Cây tiền tố
I. MỞĐẦU
Cây tiền tố (trie)được sử dụng để quản lý và phục vụ tìm kiếm nhanh các đối tượng có phần
đầu giống nhau.Ví dụ, khi tìm kiếm trên google.com, nếu ta gõ vào cửa sổ tìm kiếm ký tự “O”
hệ thống sẽ đưa ra ra một số đối tượng bắt đầu bằng chữ cái O: “Ola”, “Ongame”, “One
piece”, “Oggy”, … Nếu ta gõ tiếp “Ol” thì thông tin đưa ra sẽ là: “Olympus”, “Ola”, “Ola
me”, “Ole”, … Khi gõ “Oly” sẽ có nội dung gợi ý lựa chọn: “Olympus”, “Olympic”,
“Olympia”, “Olympus has fallen”, … Nếu nội dung gõ trong thanh tìm kiếm là “Olympiad in”
thì ở cửa sổ dự báo sẽ có nội dung: “Olympiad india”, “Olympiad in informatics”, “Olympiad
inequalities”, “Olympiad in chippenham”, …
Cây tiền tố gồm một gốc không chứa thông tin, trên mỗi cạnh lưu một ký tự, mỗi nút và
đường đi từ gốc đến nút đó thể hiện một xâu, gồm các ký tự là các ký tự thuộc cạnh trên
đường đi đó.
Việc tạo và xử lý cây tiền tố là nội dung chủ yếu của các hệ quản trị cơ sở dữ liệu văn
bản.Dưới đây ta sẽ xét một số phép xử lý đặc thù trên cây tiền tố thông qua một số bài toán cụ
thể.

II. ỨNG DỤNG CỦA CÂY TIỀN TỐ TRONG CÁC BÀI TOÁN
1. Bài toán 1:Tìm kiếm nhiều mẫu
1.1.

Đề bài (Nguồn: Truyền thống)

Cho xâu t và tập các xâu mẫu s1, s2, …, sn. Hãy đếm số lần xuất hiện của các xâu mẫu trong
xâu t.
Dữ liệu: Dòng đầu tiên chứa xâu t có độ dài không vượt quá 5×105. Dòng thứ hai ghi số
nguyên n (1 ≤ n ≤ 100). Dòng thứ i trong n dòng tiếp theo chứa xâu si có độ dài không vượt
quá 15. Các xâu si chỉ chứa các chữ cái Latin thường ‘a’..‘z’ và hoa ‘A’..‘Z’, các chữ số
‘0’..’9’ và các ký hiệu “!?.,:;-_’#$%&/=*+(){}[]”. Xâu t cũng chứa các ký tự đó và
thêm ký tự dấu cách. Chú ý rằng có thể có một số xâu mẫu giống nhau và mỗi vị trí nó xuất
hiện trong xâu t ta chỉ đếm 1 lần.

Đầu tiên chúng ta tạo một trie biểu diễn tập các xâu mẫu:
• Mỗi cạnh của trie có nhãn là một ký tự.
• Hai cạnh đi ra từ một nút có nhãn khác nhau.
• Nhãn của một nút v là ghép các nhãn của các cạnh trên đường đi từ nút gốc tới nút v
và kí hiệu là L(v). Khi đó với mỗi xâu mẫu si, tồn tại một nút v với L(v) = si.
• Nhãn L(v) của một nút lá v bất kỳ là bằng một xâu mẫu si nào đó.
Ví dụ cây trie với các xâu mẫu là “he”, “she”, “his”, “hers” như sau:
h

0

e

1

“he”
r
2

i
s

s

6
3

h

e

leaf[u] = true;
// nut u nay la diem cuoi cua mot mau
word[u] = id;
// ghi nhan chi so cua mau
}

2


Bây giờ giả sử ta cần tìm kiếm các mẫu trong xâu “shers”. Ta bắt đầu từ nút 0 và đi theo cạnh
‘s’ tới nút 3, tiếp theo từ nút 3 đi theo cạnh ‘h’ tới nút 4, rồi từ nút 4 đi theo cạnh ‘e’ tới nút 5.
Vì nút 5 là nút lá nên ta ghi nhận có một vị trí xuất hiện mẫu (chú ý đây là vị trí cuối của mẫu
xuất hiện). Nhưng từ nút 5 lại không có cạnh ‘r’ đi ra, vì vậy ta cần phải quay lui lại phía
trước xem có mẫu nào khác xuất hiện không. Việc quay lui lại là không phải từ đầu mà chỉ
quay lui lại nút có nhãn là phần hậu tố dài nhất của nút 5, tức là nút 2. Nhưng nút 2 lại là nút
lá nên ta lại ghi nhận thêm một vị trí nữa mẫu xuất hiện. Sau đó từ nút 2 ta lại đi theo cạnh ‘r’
tới nút 8, rồi từ nút 8 đi theo cạnh ‘s’ tới nút 9. Nút 9 là nút lá nên ta lại ghi nhận thêm một vị
trí nữa mẫu xuất hiện.Đến đây ta dừng việc tìm kiếm vì đã xét đến cuối xâu.
Như vậy với mỗi nút u ta cần biết nút v sao cho nhãn của nút v là phần hậu tố dài nhất của
nhãn nút u và ta đặt link[u] = v. Các đường nét đứt trong trie dưới đây là link của mỗi nút.
h

0

e

1

“he”
r

int u = q.front(); q.pop();
int v = link[u];
leaf[u] |= leaf[v];
for (int i = 0; i < 128; i++)
if (to[u][i] != 0) {
link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
q.push(to[u][i]);
}
else
to[u][i] = to[v][i];
}
}

Hàm search_str sau thể hiện việc tìm kiếm các mẫu và trả lại số mẫu xuất hiện trong xâu.
int search_str(string s) {
int cnt = 0, u = 0;
for (int i = 0; i < s.size(); i++) {
u = to[u][s[i]];
int v = u;
while (leaf[v]) {
if (word[v] != 0) cnt++;
v = link[v];
}
}
return cnt;
}

3



while (!q.empty()) {
int u = q.front(); q.pop();
int v = link[u];
leaf[u] |= leaf[v];
for (int i = 0; i < 128; i++)
if (to[u][i] != 0) {
link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
q.push(to[u][i]);
}
else
to[u][i] = to[v][i];
}
}
int search_str(string s) {
int cnt = 0, u = 0;
for (int i = 0; i < s.size(); i++) {
u = to[u][s[i]];
int v = u;
while (leaf[v]) {
if (word[v] != 0) cnt++;
v = link[v];
}
}
return cnt;
}
int main () {
freopen("find_patterns.inp", "r", stdin);
freopen("find_patterns.out", "w", stdout);

4

trong bài toán sinh học, ta cần xem các gen nào có trong DNA, …

2. Bài toán 2: Tách từ
2.1.

Đề bài (Nguồn: Croatia 2006 / Final Exam #1)

Một xâu cần được chia thành các đoạn con mà mỗi đoạn con thuộc một tập các từ cho trước.
Bạn hãy viết chương trình tính số cách khác nhau để chia một xâu cho trước. Vì số cách chia
có thể rất lớn nên bạn chỉ cần đưa số dư của nó khi chia cho 1337377.
Dữ liệu: Dòng đầu tiên chứa một xâu với độ dài tối đa 300.000 ký tự. Dòng thứ hai chứa một
số nguyên N (1 ≤ N ≤ 4000). Mỗi dòng trong N dòng tiếp theo chứa một từ trong tập. Mỗi từ
gồm nhiều nhất 100 ký tự. Không có hai từ nào giống nhau và tất cả các ký tự là các chữ cái
tiếng Anh in thường.
Kết quả: Chứa một số nguyên là số cách chia xâu thành các từ theo modun 1337377.
Ví dụ:
tach_tu.inp
abcd
4
a
b
cd
ab
afrikapaprika

tach_tu.out
2

1


Bây giờ vấn đề là kiểm tra xem từ nào là hậu tố của xâu t[0..i]. Để làm điều này, ta xây dựng
một trie cho các từ và tìm kiếm xâu t trên trie. Khi xét đến kí tự thứ i của xâu t, ta xem nút
tương ứng với ký tự này trên trie có là nút lá hay không. Nếu nó là nút lá, tức là có một từ
xuất hiện ở phần hậu tố của xâu t[0..i] và khi đó ta tính cnt[i] theo công thức trên.
Câu trả lời của bài toán là cnt[t.size()-1].
Độ phức tạp của thuật toán là O(N×100+N+ t.size()).
2.3.

Chương trình

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1337377;
string t;
int n, m, len[4001], to[400001][26], link[400001], word[400001], sz = 0,
cnt[300001];
bool leaf[400001];
void init_trie() {
memset(to, 0, sizeof(to));
memset(leaf, false, sizeof(leaf));
memset(link, 0, sizeof(link));
memset(word, 0, sizeof(word));
}
void add_str(string s, int id) {
int u = 0;
for (int i = 0; i < s.size(); i++) {
int j = s[i]-'a';
if (to[u][j] == 0) to[u][j] = ++sz;
u = to[u][j];
}

if (word[v] != 0)
if (i-len[word[v]] == -1)
cnt[i] = (cnt[i] + 1) % MOD;
else
cnt[i] = (cnt[i] + cnt[i-len[word[v]]]) % MOD;
v = link[v];
}
}
}
int main () {
freopen("tach_tu.inp", "r", stdin);
freopen("tach_tu.out", "w", stdout);
char s[300001];
scanf("%s\n%d\n", &s, &n);
t = s;
init_trie();
for (int i = 1; i
Kết quả: Ghi ra số lượng chữ cái tối thiểu cần xóa.
Ví dụ:
mat_khau.inp
12 5
afbachtdspya
aba
a
bach
dsy
zero
33 5
throughthestormwereachtheshoreyou
rough
the
storm
reach
shore

3.2.

mat_khau.out
6

7

Thuật toán

Bài toán này về cơ bản là giống bài toán “tách từ” ở trên. Ở đây ta gọi cnt[i] là số lượng tối
thiểu các chữ cái cần loại bỏ khỏi xâuP[0..i] để có được một từ mới là từ ghép của một số từ
trong từ điển. Vì vậy nếu xâu sj là một hậu tố của xâu P[0..i] thì ta có:

int u = 0;
for (int i = 0; i < s.size(); i++) {
int j = s[i]-'a';
if (to[u][j] == 0) to[u][j] = ++sz;
u = to[u][j];
}
leaf[u] = true;
word[u] = id;
}
void push_link() {
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
int v = link[u];
leaf[u] |= leaf[v];
for (int i = 0; i < 26; i++)
if (to[u][i] != 0) {
link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
q.push(to[u][i]);
}
else
to[u][i] = to[v][i];
}
}
int search_str(string s) {
int u = 0;
for (int i = 0; i < s.size(); i++) {
u = to[u][s[i]-'a'];
int v = u;

for (int i = 1; i 3.5.

Cảm nhận

Bài toán trên là ứng dụng của thuật toán quy hoạch động với cấu trúc dữ liệu cây tiền tố.

4. Bài toán 4: Biểu tượng cảm xúc
4.1.

Đề bài (Nguồn: The 2007 ACM South American Programming Contest)

Biểu tượng cảm xúc được sử dụng trong chat và e-mail để thể hiện những cảm xúc mà các từ
rất khó diễn tả. Có rất nhiều biểu tượng cảm xúc đẹp, nhưng cũng có một số biểu tượng cảm
xúc xấu khiến một số người cảm thấy thực sự khó chịu.
George là một trong số những người như vậy. Anh ta không thích các biểu tượng cảm xúc
xấu, vì vậy anh ta đang chuẩn bị một kế hoạch để loại bỏ tất cả các biểu tượng cảm xúc xấu
trong tất cả các e-mail của mình. Bạn hãy giúp anh ta làm việc này.

3 1
:)
):
))
:):)):)):)):(:((:(((:):)

4.2.

emoticons.out
11

8

Thuật toán

Duyệt các mẫu xuất hiện trong văn bản theo vị trí cuối của mẫu xuất hiện theo thứ tự tăng. Ta
sẽ thay ký tự cuối cùng của mẫu bằng dấu cách, việc này sẽ xóa được nhiều biểu tượng xấu
nhất có thể.
Vì vậy theo thuật toán Aho-Corasick, khi tìm thấy vị trí cuối một mẫu xuất hiện ta sẽ tăng
biến đếm số ký tự cần xóa lên 1 và tìm kiếm tiếp tục từ vị trí tiếp theo, tức là trạng thái mới u
= 0.
4.3.

Chương trình

#include <bits/stdc++.h>
using namespace std;
int n, m, to[1501][128], link[1501], word[1501], sz = 0, ans = 0;
bool leaf[1501];
string t;

q.push(to[u][i]);
}
else
to[u][i] = to[v][i];
}
}
int search_str(string s) {
int cnt = 0, u = 0;
for (int i = 0; i < s.size(); i++) {
u = to[u][s[i]];
int v = u;
if (leaf[v]) {
cnt++;
u = 0;
}
}
return cnt;
}
int main () {
freopen("emoticons.inp", "r", stdin);
freopen("emoticons.out", "w", stdout);
scanf("%d%d\n", &n, &m);
init_trie();
for (int i = 1; i
bị kiểm duyệt t1, t2, ..., tN, tức là bác muốn xóa chúng khỏi S. Để làm như vậy, bác John tìm sự
xuất hiện đầu tiên của một từ bị kiểm duyệt trong S (có chỉ số bắt đầu sớm nhất) và loại bỏ nó
ra khỏi S. Sau đó bác lặp lại quá trình này một lần nữa, xóa sự xuất hiện đầu tiên của một từ bị
kiểm duyệt khỏi S, lặp lại cho đến khi không xuất hiện một từ bị kiểm duyệt nào trong S. Lưu
ý rằng việc xóa một từ bị kiểm duyệt có thể tạo ra một sự xuất hiện mới của một từ bị kiểm
duyệt mà không tồn tại trước đó.
Bác John lưu ý không có từ bị kiểm duyệt nào xuất hiện như là một xâu con của một từ bị
kiểm duyệt khác. Vì vậy từ bị kiểm duyệt với chỉ số sớm nhất trong Sđược xác định duy nhất.
Hãy giúp bác John xác định nội dung cuối cùng của S sau khi hoàn tất kiểm duyệt.
Dữ liệu: Dòng đầu tiên chứa xâu S bao gồm các chữ cái tiếng Anh thường (‘a’..’z’) và có độ
dài tối đa là 105. Dòng thứ hai chứa số nguyên dương N là số từ bị kiểm duyệt. Dòng thứ i
trong N dòng tiếp theo chứa từ bị kiểm duyệt ti. Các từ bị kiểm duyệt chỉ chứa các chữ cái
tiếng Anh thường (‘a’..’z’) và tổng độ dài của tất cả các từ bị kiểm duyệt không vượt quá 10 5.
Kết quả: Ghi ra xâu S cuối cùng sau khi hoàn tất kiểm duyệt. Dữ liệu vào đảm bảo xâu S sẽ
khác rỗng sau khi hoàn tất kiểm duyệt.
Ví dụ:
kiem_duyet.inp
begintheescapexecutionatthebreakofdawn
2
escape
execution

5.2.

kiem_duyet.out
beginthatthebreakofdawn

Thuật toán

Ta sẽ xây dựng xâu kết quảR với lần lượt từng ký tự một từ xâu S. Mỗi khi xuất hiện 1 từ bị


}

memset(leaf, false, sizeof(leaf));
memset(link, 0, sizeof(link));
memset(word, 0, sizeof(word));

void add_str(string s, int id) {
int u = 0;
for (int i = 0; i < s.size(); i++) {
int j = s[i]-'a';
if (to[u][j] == 0) to[u][j] = ++sz;
u = to[u][j];
}
leaf[u] = true;
word[u] = id;
len[id] = s.size();
}
void push_link() {
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
int v = link[u];
leaf[u] |= leaf[v];
for (int i = 0; i < 26; i++)
if (to[u][i] != 0) {
link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
q.push(to[u][i]);
}

add_str(t, i);
}
push_link();
search_str(s);
printf("%s\n", r.c_str());

14


}

return 0;

5.4.

Test

Đường dẫn tải test cho bài toán:
/>5.5.

Cảm nhận

Bài toán trên cho ta thấy sự ứng dụng rất đa dạng của cấu trúc dữ liệu cây tiền tố trong xử lý
xâu.

6. Bài toán 6: Xor lớn nhất
6.1.

Đề bài (Nguồn: Sưu tầm)


ans = max(ans, a[i] xor a[j]);
printf("%d\n", ans);
return 0;
}

15


Độ phức tạp của thuật toán: O(n2).
Subtask 2:
Do 0 ≤ ai ≤ 109 nên ta coi mỗi số ai như là một dãy 31 bít. Xét lần lượt từng số ai với i = 1, 2,
…, n. Với mỗi số ai ta tìm trong các số a1, a2, …, ai-1 số nào xor với ai cho kết quả lớn nhất.
Để làm điều này ta cần tạo trie cho dãy các bít của a1, a2, …, ai-1. Xét các bít của ai từ trọng số
cao đến thấp và tìm đường đi trên trie theo dãy bít này sao cho xor cho giá trị lớn nhất. Các
chi tiết cụ thể xem chú thích trong chương trình sau.
6.3.

Chương trình

#include <bits/stdc++.h>
using namespace std;
int n, to[3100001][2], sz = 0, ans = 0;
void init_trie() {
memset(to, 0, sizeof(to));
}
void add_bit(int a) {
for (int i = 30, u = 0; i >= 0; i--) {
int j = (a >> i) & 1;
if (to[u][j] == 0) to[u][j] = ++sz;
u = to[u][j];

printf("%d\n", ans);
return 0;
}

Độ phức tạp thuật toán là: O(n×31).

16


6.4.

Test

Đường dẫn tải test cho bài toán:
/>6.5.

Cảm nhận

Bài toán này cho ta thấy ngoài việc dùng cấu trúc dữ liệu cây tiền tố để xử lý xâu, ta còn ứng
dụng vào việc xử lý các dãy bít.

7. Bài toán 7: Tổng xor
7.1.

Đề bài (Nguồn: Regionals 2009 Asia - Amritapuri)

Cho dãy A gồm n số nguyên không âm a1, a2, …, an. Hãy chọn ra một dãy con gồm các phần
tử liên tiếp của dãy A sao cho xor tất cả các phần tử của dãy con là lớn nhất, tức là tìm dãy
con ai, ai+1, …, aj (1 ≤ i ≤ j ≤ n) sao cho (aixorai+1xor … xoraj) lớn nhất.
Ở đây xor là phép tính cộng bit không nhớ (phép xor trong Pascal hay ^ trong C/C++).

#include <bits/stdc++.h>
using namespace std;
int n, to[3100001][2], sz = 0;

17


void init_trie() {
memset(to, 0, sizeof(to));
}
void add_bit(int a) {
for (int i = 30, u = 0; i >= 0; i--) {
int j = (a >> i) & 1;
if (to[u][j] == 0) to[u][j] = ++sz;
u = to[u][j];
}
}
int max_xor(int a) {
int num = 0;
for (int i = 30, u = 0; i >= 0; i--) {
int b = (a >> i) & 1;
if (to[u][1-b] != 0) {
num += 1
Là sự mở rộng của bài toán 6 qua tính chất của phép xor.
Ứng dụng của cấu trúc cây tiền tố và tính chất của phép xor.

8. Bài toán 8: Xor mảng con
8.1.

Đề bài(Nguồn: />18


Cho mảng gồm n số nguyên không âm a1, a2, …, an. Hãy tính số mảng con gồm các phần tử
liên tiếp sao cho khi xor tất cả các phần tử của mảng con được giá trị nhỏ hơn k, tức là tính số
mảng con ai, ai+1, …, aj (1 ≤ i ≤ j ≤ n) sao cho aixorai+1xor … xoraj
if (((k>>i)&1) == 1) {
// bit thu i cua k
num += cnt[u][b];
if (to[u][1-b] == 0) break;
u = to[u][1-b];

19


}
else {
if (to[u][b] == 0) break;
u = to[u][b];
}

}
return num;

}

int main() {
scanf("%d%d", &n, &k);
init_trie();
add_bit(0);
int pre = 0;
for (int i = 1; i
Ở đây xor là phép tính cộng bit không nhớ (phép xor trong Pascal hay ^ trong C/C++).
Dữ liệu: Dòng đầu tiên chứa 2 số nguyên n và x (1 ≤ n ≤ 105, 0 ≤ x ≤ 109). Dòng thứ hai chứa
n số nguyên a1, a2, ..., an (0 ≤ ai ≤ 109, i = 1÷n).
Kết quả:Đưa ra một số nguyên là số lượng cặp tìm được.
Ví dụ:

20


seg_num.inp
5 0
1 2 3 4 5
3 3
1 2 3

seg_num.out
15
2

Ràng buộc:
• Subtask 1 (50%): 1 ≤ n ≤ 103.
• Subtask 2 (50%): 1 ≤ n ≤ 105.
9.2.

Thuật toán

Về cơ bản bài toán này giống bài toán “Xor mảng con”, thay vì tính số lượng mảng con có
xor nhỏ hơn x bởi lớn hơn hoặc bằng x. Vì vậy ta chỉ cần chỉnh sửa lại đôi chút cài đặt của bài
toán trên.
9.3.

else {
if (to[u][1-b] == 0) break;
u = to[u][1-b];
}
}
return (i < 0) ? num+1 : num;
}
int main() {
freopen("seg_num.inp", "r", stdin);
freopen("seg_num.out", "w", stdout);
scanf("%d%d", &n, &x);
init_trie();

21


}

add_bit(0);
int pre = 0;
for (int i = 1; i
FIND 2
FIND 3
FIND 4

seq_xor.out
4
3
2
1
7
5
4
2

Giải thích ví dụ: Trước truy vấn XOR 6, dãy số là 1, 2, 3, 4. Sau truy vấn XOR 6, dãy số là 7,
4, 5, 2.
22


Ràng buộc:
• Subtask 1 (25%): N, Q ≤ 5000, 0 ≤ Ai ≤ 109, 0 ≤ x ≤ 109.
• Subtask 2 (40%): 0 ≤ x ≤ 100. Các subtask 2, 3 và 4 tiếp theo đều có: N ≤ 105, Q ≤ 105,
0 ≤ Ai ≤ 109.
• Subtask 3 (10%): 0 ≤ x ≤ 109, x luôn có dạng 2k.
• Subtask 4 (25%): 0 ≤ x ≤ 109.
10.2. Thuật toán
Coi mỗi số nhưmột dãy 31 bít. Dùng trie để biểu diễn n sốa[i] (mảng to[u][i]). Với mỗi nút ta
tính xem nó chứa bao nhiêu nút lá(mảngcnt[u][i]).
Duyệt trie này từ nút gốc và theo thứ tự từđiển, ta sẽđược các sốa[i] theo thứ tự tăng.
Vì phép xor có tính chất giao hoán nên mỗi phép xorx, ta không cập nhật ngay vào a[i] mà ta

u = to[u][b];
}
else {
if (to[u][1-b] == 0) return num;
u = to[u][1-b];
}
}

23


}

return num+1;

int main() {
freopen("seq_xor.inp", "r", stdin);
freopen("seq_xor.out", "w", stdout);
scanf("%d%d", &n, &x);
init_trie();
add_bit(0);
int pre = 0;
for (int i = 1; i


IV. TÀI LIỆU THAM KHẢO
1. Các bài tập sưu tầm trên Internet.
2. Kỹ thuật lập trình – Nguyễn Thanh Tùng – Trường ĐHBK Hà Nội.

25