Bài 39: Xâu chuyên sâu trong C++ và Python: Z-function, thuật toán Manacher, cây tiền tố Trie và Trie nhị phân
Lời mở đầu
Ở bài 28 em đã có hai vũ khí cho xâu: hash để so sánh xâu con trong $O(1)$ và hàm tiền tố $\pi$ để chạy KMP. Hai công cụ ấy giải được rất nhiều bài, nhưng vẫn còn những chỗ “cấn”: tìm xâu con đối xứng dài nhất bằng hash phải chặt nhị phân hai lần và vẫn có xác suất sai; muốn biết mỗi hậu tố khớp với đầu xâu được bao xa thì hàm $\pi$ trả lời rất vòng vèo; còn khi đề cho hàng trăm nghìn từ và hỏi “bao nhiêu từ bắt đầu bằng …” thì cả hash lẫn KMP đều lúng túng.
Bài này bổ sung ba công cụ chuyên sâu mà đề HSG quốc gia và chuyên Tin rất hay dùng. Z-function là “anh em họ” của hàm tiền tố mà bài 28 mới nhắc qua trong một khung mẹo, hôm nay ta học kỹ. Thuật toán Manacher tìm mọi xâu con đối xứng trong $O(n)$, chính xác tuyệt đối. Trie (cây tiền tố) lưu cả một từ điển, và phiên bản Trie nhị phân của nó coi mỗi số là một xâu bit, kết hợp với các phép toán bit ở bài 20 để giải các bài XOR kinh điển. Nếu em còn lúng túng với các thao tác cơ bản trên string thì nên xem lại bài 8 trước nhé.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Z-function và hộp [l, r]
Định nghĩa. Cho xâu $s$ dài $n$ (đánh số từ 0). Với mỗi vị trí $i$, $z[i]$ là độ dài tiền tố chung dài nhất của cả xâu $s$ và hậu tố $s[i..n-1]$. Nói cách khác: đặt đầu xâu thẳng dưới vị trí $i$ rồi đếm xem khớp được bao nhiêu ký tự liên tiếp. Ta quy ước $z[0] = n$ (một số tài liệu để $z[0] = 0$; quy ước nào cũng được, miễn nhất quán).
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| s[i] | a | a | b | x | a | a | b |
| z[i] | 7 | 1 | 0 | 0 | 3 | 1 | 0 |
| khớp | cả xâu | a | – | – | aab | a | – |
Bảng 1. Z-function của aabxaab. Ví dụ $z[4] = 3$: hậu tố aab bắt đầu tại 4 trùng với 3 ký tự đầu aab của xâu.
Cách ngây thơ là với mỗi $i$ so từ đầu: $O(n^2)$ khi xâu toàn chữ a. Mấu chốt để xuống $O(n)$ là tận dụng những gì đã khớp, giống tinh thần của KMP, nhưng hình ảnh trực quan hơn nhiều: một cái hộp.
Hộp [l, r]. Trong lúc tính, ta luôn giữ đoạn $s[l..r]$ là một đoạn đã biết chắc trùng với tiền tố $s[0..r-l]$ (tức là $z[l] \ge r - l + 1$), và chọn đoạn có $r$ xa nhất từng gặp. Khi xét vị trí $i$:
- $i > r$ (ngoài hộp): chưa biết gì, đặt $z[i] = 0$ và so từng ký tự như cách ngây thơ.
- $i \le r$ (trong hộp): vì $s[l..r] = s[0..r-l]$ nên đoạn $s[i..r]$ giống hệt đoạn $s[i-l..r-l]$ ở đầu xâu. Mà $z[i-l]$ đã tính rồi! Vậy ta được mượn ngay $z[i] \ge \min(r - i + 1,\ z[i-l])$. Lấy $\min$ vì ngoài phạm vi hộp ta không biết gì cả.
- Sau đó vẫn so tiếp từng ký tự từ vị trí $z[i]$ (chỉ thực sự chạy khi chạm mép hộp). Nếu đoạn khớp vượt quá $r$ thì dời hộp: $l = i$, $r = i + z[i] - 1$.
Hình 1. Với $s$ = aabxaabxaab, sau khi tính $z[4] = 7$ ta có hộp $[l, r] = [4, 10]$ (xanh dương). Đặt tiền tố $s[0..6]$ thẳng dưới hộp (xanh lá): hai đoạn giống hệt nhau. Xét $i = 5$ (vàng) nằm trong hộp: ô ngay dưới nó là vị trí $i - l = 1$ của tiền tố (cũng vàng), nên $z[5] \ge \min(10 - 5 + 1, z[1]) = \min(6, 1) = 1$. Và vì $z[1] = 1 < 6$ nên chắc chắn $z[5] = 1$, chỉ cần một phép so để xác nhận.
| i | hộp trước | giá trị mượn | so thêm (khớp) | z[i] | hộp sau |
|---|---|---|---|---|---|
| 1 | – | ngoài hộp: 0 | 1 | 1 | [1, 1] |
| 2 | [1, 1] | ngoài hộp: 0 | 0 | 0 | [1, 1] |
| 3 | [1, 1] | ngoài hộp: 0 | 0 | 0 | [3, 2] |
| 4 | [3, 2] | ngoài hộp: 0 | 7 | 7 | [4, 10] |
| 5 | [4, 10] | min(6, z[1] = 1) = 1 | 0 | 1 | [4, 10] |
| 6 | [4, 10] | min(5, z[2] = 0) = 0 | 0 | 0 | [4, 10] |
| 7 | [4, 10] | min(4, z[3] = 0) = 0 | 0 | 0 | [4, 10] |
| 8 | [4, 10] | min(3, z[4] = 7) = 3 | 0 | 3 | [4, 10] |
| 9 | [4, 10] | min(2, z[5] = 1) = 1 | 0 | 1 | [4, 10] |
| 10 | [4, 10] | min(1, z[6] = 0) = 0 | 0 | 0 | [4, 10] |
Bảng 2. Từng bước tính Z-function của aabxaabxaab. Cột “so thêm” chỉ đếm các lần so khớp; ngoài ra mỗi $i$ có tối đa một lần so khác để dừng. Để ý từ $i = 5$ tới $i = 10$, phần lớn giá trị đều mượn được, gần như không phải so.
Đọc thì dễ hiểu, nhưng tự tay thấy hộp trượt mới thấm. Em bấm Tiếp từng bước, chú ý lúc ô $z$ được mượn (xanh dương) và lúc hộp bị đẩy sang phải; thử thêm xâu aaaaaaaa để thấy ngay cả trường hợp “ác” nhất cho cách ngây thơ cũng chỉ tốn khoảng $2n$ phép so:
Xem code C++ / Python: z-function trong $O(n)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n; // quy ước: cả xâu trùng với chính nó
int l = 0, r = 0; // hộp [l, r]: s[l..r] = s[0..r-l], r xa nhất
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]); // mượn kết quả ở vị trí đối ứng i - l
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; // so tiếp phần chưa biết
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; } // đẩy hộp sang phải
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
vector<int> z = zFunction(s);
for(int x : z) cout << x << " ";
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n # quy ước: cả xâu trùng với chính nó
l = r = 0 # hộp [l, r]: s[l..r] = s[0..r-l], r xa nhất
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l]) # mượn kết quả ở vị trí đối ứng i - l
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1 # so tiếp phần chưa biết
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1 # đẩy hộp sang phải
return z
s = sys.stdin.readline().strip()
print(*z_function(s))Vì sao $O(n)$? Có hai khả năng khi $i$ nằm trong hộp. Nếu $z[i-l] < r - i + 1$ thì giá trị mượn đã là đáp án: vòng while chỉ so đúng một lần (khác) rồi dừng. Ngược lại, $z[i]$ bắt đầu từ $r - i + 1$, tức là phép so đầu tiên đã ở ngoài hộp. Như vậy mọi lần so khớp đều chạm tới một ký tự ở vị trí lớn hơn $r$, và ngay sau đó $r$ được đẩy tới vị trí ấy. $r$ chỉ tăng và không vượt $n$, nên tổng số lần so khớp $\le n$; mỗi $i$ thêm tối đa một lần so khác. Tổng cộng $\le 2n$ phép so.
Tìm mẫu bằng P#T. Muốn tìm mẫu $p$ (dài $m$) trong văn bản $t$, ta tính $z$ của xâu $p + $ # $+ t$, với # là ký tự không xuất hiện trong cả hai. Ký tự # như một bức tường: không $z[i]$ nào ở phần $t$ vượt quá $m$. Vị trí $i$ (trong xâu ghép) có $z[i] = m$ nghĩa là $p$ xuất hiện trong $t$ bắt đầu tại $i - m - 1$ (đánh số từ 0). Thời gian $O(n + m)$, đúng như KMP, mà code chỉ là “tính $z$ rồi duyệt”.
Hình 2. $p$ = aba, $t$ = ababa. Mảng $z$ của aba#ababa (ô đầu là $z[0] = 9$). Hai vị trí 4 và 6 có $z = 3 = m$ (xanh lá): mẫu xuất hiện trong $t$ tại 0 và 2 (từ 0), tức 1 và 3 nếu đánh số từ 1.
Xem code C++ / Python: tìm mọi vị trí của mẫu bằng z của P#T (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n;
int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; }
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string t, p;
cin >> t >> p;
int n = t.size(), m = p.size();
vector<int> z = zFunction(p + "#" + t); // '#' không có trong p và t
vector<int> pos;
for(int i = m + 1; i < m + 1 + n; i++)
if(z[i] == m) pos.push_back(i - m); // vị trí trong t, đánh số từ 1
cout << pos.size() << "\n";
for(int x : pos) cout << x << " ";
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
data = sys.stdin.read().split()
t, p = data[0], data[1]
n, m = len(t), len(p)
z = z_function(p + '#' + t) # '#' không có trong p và t
pos = [i - m for i in range(m + 1, m + 1 + n) if z[i] == m] # đánh số từ 1
print(len(pos))
print(*pos)z[0] = n; int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]); // mượn
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; // so tiếp
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; } // dời hộp
}p + "#" + t, vị trí nào có $z = |p|$ là một lần xuất hiện.while(s[z[i]] == s[i + z[i]]) mà quên điều kiện i + z[i] < n: đọc ra ngoài xâu. 3. Quên ký tự ngăn cách # (hoặc chọn ký tự có xuất hiện trong dữ liệu): $z$ ở phần $t$ có thể vượt $m$ và tràn sang chính $t$, đếm sai.Phần 2Ứng dụng của Z-function
Mảng $z$ trả lời rất “thẳng” những câu hỏi dạng so một hậu tố với đầu xâu. Dưới đây là các ứng dụng hay gặp nhất.
1. Chu kỳ của xâu. Số $k$ ($1 \le k \le n$) là một chu kỳ của $s$ khi $s[i] = s[i + k]$ với mọi $i$ hợp lệ, tức là hậu tố bắt đầu tại $k$ trùng với tiền tố cùng độ dài: $k + z[k] = n$ (với $k = n$ luôn đúng). Chu kỳ nhỏ nhất là $k$ nhỏ nhất thoả điều kiện đó. Nếu đề hỏi xâu có phải là $n/k$ bản sao ghép lại của $s[0..k-1]$ không thì thêm điều kiện $k$ chia hết $n$.
| k | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| z[k] | 0 | 0 | 5 | 0 | 0 | 2 | 0 |
| k + z[k] | 1 | 2 | 8 | 4 | 5 | 8 | 7 |
Bảng 3. $s$ = abcabcab ($n = 8$). Các $k$ có $k + z[k] = 8$ là 3 và 6: xâu có chu kỳ 3 và 6, chu kỳ nhỏ nhất là 3. Nhưng 3 không chia hết 8 nên $s$ không phải là ghép các bản sao của abc (thiếu một chữ c ở cuối).
2. Đếm số lần xuất hiện của mọi tiền tố. Bài 28 làm việc này bằng hàm $\pi$ với bước “cộng dồn theo cây đường viền” khá khó nhớ. Với $z$ thì rất tự nhiên: tại vị trí $i$, các tiền tố dài $1, 2, \ldots, z[i]$ đều xuất hiện bắt đầu từ $i$. Vậy số lần xuất hiện của tiền tố dài $L$ chính là số vị trí $i$ có $z[i] \ge L$ (tính cả $i = 0$ với $z[0] = n$). Đếm $\text{cnt}[z[i]]$ rồi cộng dồn từ phải sang trái là xong, $O(n)$.
Xem code C++ / Python: đếm số lần xuất hiện của mọi tiền tố bằng z (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n;
int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; }
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> z = zFunction(s); // z[0] = n
vector<int> cnt(n + 2, 0);
for(int i = 0; i < n; i++) cnt[z[i]]++; // vị trí i chứa mọi tiền tố dài 1..z[i]
for(int L = n - 1; L >= 1; L--) cnt[L] += cnt[L + 1]; // cnt[L] = số i có z[i] >= L
for(int L = 1; L <= n; L++) cout << cnt[L] << " ";
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
s = sys.stdin.readline().strip()
n = len(s)
cnt = [0] * (n + 2)
for v in z_function(s): # z[0] = n
cnt[v] += 1 # vị trí này chứa mọi tiền tố dài 1..v
for L in range(n - 1, 0, -1):
cnt[L] += cnt[L + 1] # cnt[L] = số vị trí có z >= L
print(*cnt[1:n + 1])3. Tiền tố chung của hai xâu bất kỳ vị trí. Muốn biết đoạn bắt đầu tại $i$ của $t$ khớp với đầu xâu $p$ được bao xa (với mọi $i$), lại dùng $z$ của $p + $ # $+ t$. Làm thêm một lần với hai xâu đảo ngược sẽ biết đoạn kết thúc tại $j$ khớp với cuối $p$ được bao xa. Ghép hai thông tin này giải được bài “tìm mẫu sai tối đa một ký tự” (bài tập 6) và bài “thêm ít ký tự nhất để thành xâu đối xứng” (bài tập 5).
| Câu hỏi | Hàm tiền tố π (bài 28) | Z-function |
|---|---|---|
| Tìm mọi vị trí của mẫu | KMP hoặc π của p#t | z của p#t |
| Chu kỳ nhỏ nhất | $n - \pi[n-1]$ | $k$ nhỏ nhất có $k + z[k] = n$ |
| Đếm lần xuất hiện mọi tiền tố | cộng dồn theo đường viền, khó nhớ | đếm $z[i] \ge L$, rất tự nhiên |
| Hậu tố tại $i$ khớp đầu xâu bao xa | không trả lời trực tiếp | chính là $z[i]$ |
| Xử lý luồng ký tự đến dần (online) | được: thêm ký tự là tính tiếp | không, cần biết cả xâu |
| Độ khó cài đặt | ngắn, dễ nhầm $\pi[j-1]$ | ngắn, dễ nhầm $\min$ và biên |
Bảng 4. Hàm tiền tố hay Z-function? Hai công cụ giải được hầu hết các bài của nhau; em nên thuộc cả hai và chọn cái cho lời giải tự nhiên hơn.
Phần 3Thuật toán Manacher: xâu con đối xứng trong O(n)
Bài toán. Tìm xâu con liên tiếp đối xứng (palindrome) dài nhất của $s$, hoặc đếm mọi xâu con đối xứng. Bài tập 7 của bài 28 làm bằng hash + chặt nhị phân trong $O(n \log n)$, có xác suất sai, và phải chặt riêng độ dài chẵn, lẻ. Manacher làm trong $O(n)$, chính xác, và ý tưởng lại giống hệt Z-function: mượn kết quả nhờ một cái hộp.
Bước 1: mở rộng từ tâm, $O(n^2)$. Với mỗi tâm, mở rộng sang hai bên chừng nào hai đầu còn bằng nhau. Phiền ở chỗ xâu đối xứng độ dài lẻ có tâm là một ký tự (aba), còn độ dài chẵn có tâm nằm giữa hai ký tự (abba), nên phải viết hai vòng lặp.
Bước 2: chèn ký tự #. Biến $s$ thành $t$ bằng cách chèn # vào đầu, cuối và giữa mọi cặp ký tự: abba → #a#b#b#a#. Bây giờ abba có tâm là dấu # ở giữa, aba có tâm là chữ b: mọi xâu đối xứng của $s$ đều có đúng một tâm trong $t$. Gọi $d[i]$ là bán kính lớn nhất sao cho $t[i - d[i] .. i + d[i]]$ đối xứng. Một điều rất đẹp: $d[i]$ đúng bằng độ dài xâu đối xứng tương ứng trong $s$, và nó bắt đầu tại vị trí $(i - d[i]) / 2$ của $s$.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| t[i] | # | a | # | b | # | a | # | c | # | a | # | b | # | b | # |
| d[i] | 0 | 1 | 0 | 3 | 0 | 1 | 0 | 5 | 0 | 1 | 0 | 1 | 2 | 1 | 0 |
Bảng 5. $s$ = abacabb, $t$ = #a#b#a#c#a#b#b#. $d$ lớn nhất là $d[7] = 5$ (tâm là chữ c): xâu bacab bắt đầu tại $(7 - 5)/2 = 1$ trong $s$. Xâu đối xứng chẵn bb có tâm là dấu # tại $i = 12$, $d[12] = 2$.
Bước 3: soi gương qua tâm hộp. Giữ hộp $[l, r]$ là xâu đối xứng (trong $t$) có đầu phải $r$ xa nhất đã tìm được, tâm của nó là $C = (l + r) / 2$. Khi xét tâm $i$:
- $i > r$: chưa biết gì, $k = 0$ rồi mở rộng như bước 1.
- $i \le r$: lấy điểm đối xứng của $i$ qua $C$ là $j = l + r - i$ (đã tính $d[j]$). Vì cả hộp là một xâu đối xứng, nửa trái là ảnh gương của nửa phải, nên xâu đối xứng tâm $j$ cũng có “bản sao” tâm $i$, ít nhất là trong phạm vi hộp: $k = \min(d[j],\ r - i)$. Rồi mới mở rộng tiếp từ đó.
- Nếu $i + k > r$ thì dời hộp: $l = i - k$, $r = i + k$.
Hình 3. $s$ = abacabb. Khi xét $i = 11$, hộp là $[l, r] = [2, 12]$ (xanh dương), chính là xâu đối xứng tâm $C = 7$ (bacab trong $s$). Ảnh gương của $i$ là $j = 2 + 12 - 11 = 3$. Xâu đối xứng tâm $j$ có $d[3] = 3$ (#a#b#a#), nhưng hai ô đỏ đầu tiên của nó đã thò ra ngoài mép trái hộp, nên gương chỉ đảm bảo $k = \min(d[j], r - i) = \min(3, 1) = 1$. Thử mở rộng tiếp: $t[9] = $ a ≠ $t[13] = $ b (đỏ), dừng, $d[11] = 1$. Nếu mượn nguyên $d[j] = 3$ thì đã sai.
Tại sao phải lấy $\min$ với $r - i$? Vì gương chỉ đảm bảo trong phạm vi hộp. Phần xâu đối xứng tâm $j$ thò ra ngoài mép trái hộp thì ảnh của nó nằm ngoài mép phải, nơi ta chưa kiểm tra gì. Độ phức tạp $O(n)$ với cùng lý do như Z-function: mỗi lần mở rộng thành công đều đẩy $r$ sang phải, mà $r$ không vượt quá $2n$.
Em xem mô phỏng dưới đây, chú ý ba chữ cái đánh dấu phía trên: C là tâm hộp, i là tâm đang xét, j là ảnh gương của i. Có lúc $d[j]$ được mượn trọn vẹn và không phải mở rộng thêm ô nào:
Xem code C++ / Python: thuật toán Manacher tìm xâu con đối xứng dài nhất $O(n)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
string t = "#";
for(char c : s){ t += c; t += '#'; } // "abba" -> "#a#b#b#a#"
int m = t.size();
vector<int> d(m, 0); // d[i]: bán kính lớn nhất, t[i-d..i+d] đối xứng
int l = 0, r = -1; // hộp [l, r]: xâu đối xứng có đầu phải xa nhất
for(int i = 0; i < m; i++){
int k = (i > r) ? 0 : min(d[l + r - i], r - i); // soi gương qua tâm hộp
while(i - k - 1 >= 0 && i + k + 1 < m && t[i - k - 1] == t[i + k + 1]) k++;
d[i] = k;
if(i + k > r){ l = i - k; r = i + k; }
}
int best = 0, center = 0;
for(int i = 0; i < m; i++) if(d[i] > best){ best = d[i]; center = i; }
cout << best << "\n" << s.substr((center - best) / 2, best); // d[i] = độ dài trong s
return 0;
}import sys
s = sys.stdin.readline().strip()
t = '#' + '#'.join(s) + '#' # "abba" -> "#a#b#b#a#"
m = len(t)
d = [0] * m # d[i]: bán kính lớn nhất, t[i-d..i+d] đối xứng
l, r = 0, -1 # hộp [l, r]: xâu đối xứng có đầu phải xa nhất
for i in range(m):
k = 0 if i > r else min(d[l + r - i], r - i) # soi gương qua tâm hộp
while i - k - 1 >= 0 and i + k + 1 < m and t[i - k - 1] == t[i + k + 1]:
k += 1
d[i] = k
if i + k > r:
l, r = i - k, i + k
best = max(d)
center = d.index(best)
start = (center - best) // 2 # d[i] chính là độ dài trong s
print(best)
print(s[start:start + best])t = "#" + (mỗi ký tự c của s nối thêm c + "#");
int l = 0, r = -1;
for(int i = 0; i < m; i++){
int k = (i > r) ? 0 : min(d[l + r - i], r - i); // soi gương
while(i-k-1 >= 0 && i+k+1 < m && t[i-k-1] == t[i+k+1]) k++;
d[i] = k;
if(i + k > r){ l = i - k; r = i + k; } // dời hộp
}long long. 3. Đề hỏi xâu đối xứng xuất hiện đầu tiên thì lấy tâm nhỏ nhất có $d$ lớn nhất (so sánh bằng >, không phải >=).Phần 4Trie: cây tiền tố
Bây giờ đổi đề: không phải một xâu dài, mà là rất nhiều xâu ngắn (một từ điển). Câu hỏi: từ $w$ có trong từ điển không? Bao nhiêu từ bắt đầu bằng $p$? Có từ nào là tiền tố của từ khác không? Cho tất cả vào set rồi duyệt thì câu “bao nhiêu từ bắt đầu bằng $p$” rất chậm. Cấu trúc dành riêng cho việc này là trie.
Cấu trúc. Trie là một cây có gốc. Mỗi cạnh mang một chữ cái, các cạnh đi ra từ cùng một nút mang chữ cái khác nhau. Đi từ gốc xuống một nút, ghép các chữ cái trên đường đi được một xâu: mỗi nút ứng với đúng một tiền tố của các từ đã chèn. Các từ có chung tiền tố thì dùng chung đoạn đường đầu. Mỗi nút lưu thêm:
cntPass[u]: số từ đi qua nút $u$ = số từ có tiền tố ứng với $u$;cntEnd[u]: số từ kết thúc đúng tại $u$ (để phân biệt từanvới tiền tốancủaant).
Hình 4. Trie của 5 từ an, ant, and, bat, ban. Nút có vòng xanh lá là nơi một từ kết thúc. Nút n dưới a có cnt = 3: ba từ an, ant, and có tiền tố an.
Ba thao tác, mỗi thao tác chỉ đi một đường từ gốc xuống nên tốn $O(|w|)$, không phụ thuộc từ điển lớn cỡ nào:
- Chèn $w$: đi từ gốc theo từng chữ cái; cạnh chưa có thì tạo nút mới. Tăng
cntPasscủa mọi nút trên đường đi, cuối cùng tăngcntEndcủa nút cuối. - Tìm $w$: đi theo từng chữ cái; gặp cạnh không có thì trả lời không. Đi hết thì xem
cntEndcủa nút cuối có lớn hơn 0 không. - Đếm số từ có tiền tố $p$: đi theo $p$; nếu đi hết thì đáp án là
cntPasscủa nút cuối, ngược lại là 0.
Em nhập các từ của mình vào mô phỏng để xem lúc nào trie tạo nút mới, lúc nào chỉ đi theo đường có sẵn, và vì sao đếm tiền tố chỉ tốn $|p|$ bước:
Cài đặt. Cách nhanh nhất trong C++ là dùng mảng tĩnh nxt[u][c] = chỉ số nút con theo chữ $c$ (0 nghĩa là chưa có, vì gốc là nút 0 và không bao giờ là con của ai). Số nút tối đa bằng tổng độ dài các từ cộng 1. Trong Python, mỗi nút giữ một dict từ chữ cái sang nút con.
Xem code C++ / Python: trie: chèn, tìm từ, đếm số từ có tiền tố (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005; // tổng độ dài các từ + 1
int nxt[MAXN][26]; // nxt[u][c]: nút con theo chữ c (0 = chưa có)
int cntPass[MAXN], cntEnd[MAXN]; // số từ đi qua / kết thúc tại nút
int numNodes = 1; // nút 0 là gốc
void insertWord(const string &w){
int u = 0;
for(char ch : w){
int c = ch - 'a';
if(!nxt[u][c]) nxt[u][c] = numNodes++; // chưa có cạnh thì tạo nút mới
u = nxt[u][c];
cntPass[u]++;
}
cntEnd[u]++;
}
int walk(const string &p){ // nút ứng với xâu p, -1 nếu không có
int u = 0;
for(char ch : p){
int c = ch - 'a';
if(!nxt[u][c]) return -1;
u = nxt[u][c];
}
return u;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n;
for(int i = 0; i < n; i++){ string w; cin >> w; insertWord(w); }
cin >> q;
while(q--){
int type; string p;
cin >> type >> p;
int u = walk(p);
if(type == 1) cout << (u != -1 && cntEnd[u] > 0 ? "YES" : "NO") << "\n"; // có từ p?
else cout << (u == -1 ? 0 : cntPass[u]) << "\n"; // bao nhiêu từ có tiền tố p?
}
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
nxt = [{}] # nxt[u]: dict chữ cái -> nút con
cnt_pass = [0] # số từ đi qua nút
cnt_end = [0] # số từ kết thúc tại nút
for w in data[1:n + 1]:
u = 0
for ch in w:
v = nxt[u].get(ch)
if v is None: # chưa có cạnh thì tạo nút mới
v = len(nxt)
nxt[u][ch] = v
nxt.append({}); cnt_pass.append(0); cnt_end.append(0)
u = v
cnt_pass[u] += 1
cnt_end[u] += 1
def walk(p): # nút ứng với p, -1 nếu không có
u = 0
for ch in p:
u = nxt[u].get(ch, -1)
if u == -1:
return -1
return u
q = int(data[n + 1])
out = []
pos = n + 2
for _ in range(q):
typ, p = data[pos], data[pos + 1]
pos += 2
u = walk(p)
if typ == '1':
out.append('YES' if u != -1 and cnt_end[u] > 0 else 'NO')
else:
out.append(str(0 if u == -1 else cnt_pass[u]))
print('\n'.join(out))
main()nxt[MAXN][26] kiểu int tốn $26 \cdot 4 = 104$ byte mỗi nút. Tổng độ dài $10^6$ thì tốn khoảng 104 MB, dễ vượt giới hạn 256 MB khi cộng thêm các mảng khác, và chắc chắn vượt nếu giới hạn là 64 MB. Cách xử lý: đọc kỹ giới hạn tổng độ dài; nếu bảng chữ cái lớn hoặc từ rất dài, dùng map<char,int> hoặc danh sách cạnh cho mỗi nút (chậm hơn nhưng tiết kiệm). Muốn xoá một từ thì chỉ cần đi theo từ đó và giảm cntPass, cntEnd, không cần xoá nút.Phần 5Trie nhị phân và cặp XOR lớn nhất
Bài toán. Cho $n$ số nguyên không âm ($n \le 10^5$, $a_i < 2^{30}$). Tìm giá trị lớn nhất của $a_i \oplus a_j$ (phép XOR, ^ trong C++/Python) với $i \ne j$. Hai vòng for tốn $O(n^2) = 10^{10}$: quá chậm.
Coi mỗi số là một xâu bit. Viết mỗi số thành đúng 30 bit, từ bit cao nhất (bit 29) xuống bit thấp nhất (bit 0), rồi chèn vào một trie mà mỗi nút chỉ có hai con: 0 và 1. Đó là trie nhị phân. Nó có tối đa $30n + 1$ nút.
Tham lam từ bit cao xuống. Với một số $x$, muốn tìm $y$ trong trie để $x \oplus y$ lớn nhất. Bit cao có giá trị lớn hơn tổng tất cả các bit thấp hơn cộng lại ($2^b > 2^{b-1} + \cdots + 1$), nên ta ưu tiên làm cho bit cao nhất của kết quả bằng 1 bằng mọi giá. Đi từ gốc xuống, ở bit $b$, nếu bit của $x$ là $c$ thì ưu tiên đi nhánh $1 - c$ (khác bit, XOR được 1); nhánh đó không có thì đành đi nhánh $c$ (XOR được 0). Mỗi truy vấn tốn 30 bước.
| bit | bit của x = 5 | muốn đi nhánh | nhánh đó có số nào? | quyết định | x XOR y (tạm) |
|---|---|---|---|---|---|
| 4 | 0 | 1 | có (25) | đi nhánh 1, kết quả +16 | 16 |
| 3 | 0 | 1 | có (25) | đi nhánh 1, kết quả +8 | 24 |
| 2 | 1 | 0 | có (25) | đi nhánh 0, kết quả +4 | 28 |
| 1 | 0 | 1 | không | đành đi nhánh 0 | 28 |
| 0 | 1 | 0 | không | đành đi nhánh 1 | 28 |
Bảng 6. Trie chứa {3, 10, 25, 2, 8} viết bằng 5 bit (25 = 11001, 5 = 00101). Truy vấn $x = 5$: hai bit đầu đều đi được nhánh ngược nên chỉ còn số 25; kết quả $5 \oplus 25 = 28$, và đó cũng là cặp XOR lớn nhất của cả dãy {3, 10, 5, 25, 2, 8}.
Thuật toán. Duyệt các số theo thứ tự; với $a_i$, hỏi trie (đang chứa $a_1, \ldots, a_{i-1}$) xem XOR lớn nhất được bao nhiêu, rồi mới chèn $a_i$ vào. Mỗi cặp $(j, i)$ với $j < i$ đều được xét ở lúc duyệt tới $i$. Tổng $O(30n)$.
Xem code C++ / Python: cặp xor lớn nhất bằng trie nhị phân (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30; // a[i] < 2^30
const int MAXNODE = 100005 * LOG + 5;
int nxt[MAXNODE][2], numNodes = 1; // nút 0 là gốc
void insertNum(int x){
int u = 0;
for(int b = LOG - 1; b >= 0; b--){ // đi từ bit cao xuống bit thấp
int c = (x >> b) & 1;
if(!nxt[u][c]) nxt[u][c] = numNodes++;
u = nxt[u][c];
}
}
int maxXor(int x){ // max (x XOR y) với y đã có trong trie
int u = 0, res = 0;
for(int b = LOG - 1; b >= 0; b--){
int c = (x >> b) & 1;
if(nxt[u][c ^ 1]){ res |= 1 << b; u = nxt[u][c ^ 1]; } // tham lam: đi nhánh ngược bit
else u = nxt[u][c];
}
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(auto &x : a) cin >> x;
int best = 0;
insertNum(a[0]);
for(int i = 1; i < n; i++){
best = max(best, maxXor(a[i])); // ghép a[i] với một số đứng trước nó
insertNum(a[i]);
}
cout << best;
return 0;
}import sys
LOG = 30 # a[i] < 2^30
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
ch = [[0, 0]] # ch[u][c]: nút con theo bit c (0 = chưa có)
def insert(x):
u = 0
for b in range(LOG - 1, -1, -1): # từ bit cao xuống bit thấp
c = (x >> b) & 1
if not ch[u][c]:
ch[u][c] = len(ch)
ch.append([0, 0])
u = ch[u][c]
def max_xor(x):
u, res = 0, 0
for b in range(LOG - 1, -1, -1):
c = (x >> b) & 1
if ch[u][c ^ 1]: # tham lam: đi nhánh ngược bit
res |= 1 << b
u = ch[u][c ^ 1]
else:
u = ch[u][c]
return res
best = 0
insert(a[0])
for x in a[1:]:
best = max(best, max_xor(x))
insert(x)
print(best)
main()for(int b = LOG - 1; b >= 0; b--){ // luôn đi từ bit CAO xuống
int c = (x >> b) & 1;
if(nxt[u][c ^ 1]){ res |= 1 << b; u = nxt[u][c ^ 1]; } // ưu tiên nhánh ngược
else u = nxt[u][c];
}long long, 1LL << b. 3. Mảng có $n \cdot \text{LOG}$ nút: với $n = 2 \cdot 10^5$, LOG = 30 là $6 \cdot 10^6$ nút × 2 số int = 48 MB, vẫn ổn. 4. Trong Python, mỗi số tốn 30 vòng lặp nên $n = 10^5$ đã mất vài giây; nên chạy bằng PyPy hoặc dùng C++ khi đi thi.- Xâu Đối Xứng (Dễ)
- Software (SOFTWARE) (Olympic 30/4 2023 – Tin học khối 10) (Trung bình)
- Chuỗi Con Xuất Hiện K Lần (DTKSUB) (Khá)
- Xâu Đối Xứng (XDXUNG) (HSG12 Lâm Đồng 2025 – Bài 3) (Khá)
- Đếm Xâu Tốt (Khó)
- Palindrome Kép (Khó)
Bài tậpLuyện Z-function, Manacher và Trie
Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$) và $q$ truy vấn ($q \le 10^5$). Mỗi truy vấn là một số $i$ ($1 \le i \le |s|$, đánh số từ 1): in độ dài tiền tố chung dài nhất của $s$ và hậu tố của $s$ bắt đầu tại vị trí $i$. Dòng 1 chứa $s$, dòng 2 chứa $q$, dòng 3 chứa $q$ số $i$.
abacaba
4
1 5 3 27
3
1
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abacaba là [7, 0, 1, 0, 3, 0, 1]: vị trí 5 là hậu tố aba khớp 3 ký tự đầu.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n;
int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; }
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
int q;
cin >> s >> q;
vector<int> z = zFunction(s);
while(q--){
int i;
cin >> i;
cout << z[i - 1] << "\n"; // đề đánh số từ 1
}
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
data = sys.stdin.read().split()
s, q = data[0], int(data[1])
z = z_function(s)
print('\n'.join(str(z[int(x) - 1]) for x in data[2:2 + q]))Danh bạ có $n$ số điện thoại ($n \le 10^5$), mỗi số là một xâu chữ số dài từ 1 tới 10. Danh bạ gọi là nhất quán nếu không có số nào là tiền tố của một số khác (hai số giống hệt nhau cũng coi là không nhất quán, vì số này là tiền tố của số kia). In YES nếu danh bạ nhất quán, ngược lại in NO.
3
0123
456
01234NO📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
0123 còn con 4 của 01234. Cách khác cũng hay: sắp xếp các xâu theo thứ tự từ điển rồi chỉ cần kiểm tra từng cặp đứng kề nhau.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int nxt[MAXN][10], cntEnd[MAXN], numNodes = 1;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; i++){
string w;
cin >> w;
int u = 0;
for(char ch : w){
int c = ch - '0';
if(!nxt[u][c]) nxt[u][c] = numNodes++;
u = nxt[u][c];
}
cntEnd[u]++;
}
bool ok = true;
for(int u = 0; u < numNodes && ok; u++){
if(!cntEnd[u]) continue;
if(cntEnd[u] > 1) ok = false; // hai số trùng nhau
for(int c = 0; c < 10; c++) if(nxt[u][c]) ok = false; // số kết thúc ở u là tiền tố của số khác
}
cout << (ok ? "YES" : "NO");
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
nxt = [{}]
end = [0]
for w in data[1:n + 1]:
u = 0
for ch in w:
v = nxt[u].get(ch)
if v is None:
v = len(nxt)
nxt[u][ch] = v
nxt.append({}); end.append(0)
u = v
end[u] += 1
ok = all(not end[u] or (end[u] == 1 and not nxt[u]) for u in range(len(nxt)))
print('YES' if ok else 'NO')Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$). Tìm xâu con liên tiếp đối xứng dài nhất. Dòng 1 in độ dài, dòng 2 in xâu đó; nếu có nhiều đáp án, in xâu xuất hiện đầu tiên (vị trí bắt đầu nhỏ nhất).
cabbadac4
abba📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abba (độ dài 4) dài hơn ada (độ dài 3). So với hash + chặt nhị phân ở bài 28, lời giải này $O(n)$ và không có xác suất sai.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
string t = "#";
for(char c : s){ t += c; t += '#'; } // "abba" -> "#a#b#b#a#"
int m = t.size();
vector<int> d(m, 0); // d[i]: bán kính lớn nhất, t[i-d..i+d] đối xứng
int l = 0, r = -1; // hộp [l, r]: xâu đối xứng có đầu phải xa nhất
for(int i = 0; i < m; i++){
int k = (i > r) ? 0 : min(d[l + r - i], r - i); // soi gương qua tâm hộp
while(i - k - 1 >= 0 && i + k + 1 < m && t[i - k - 1] == t[i + k + 1]) k++;
d[i] = k;
if(i + k > r){ l = i - k; r = i + k; }
}
int best = 0, center = 0;
for(int i = 0; i < m; i++) if(d[i] > best){ best = d[i]; center = i; }
cout << best << "\n" << s.substr((center - best) / 2, best); // d[i] = độ dài trong s
return 0;
}import sys
s = sys.stdin.readline().strip()
t = '#' + '#'.join(s) + '#' # "abba" -> "#a#b#b#a#"
m = len(t)
d = [0] * m # d[i]: bán kính lớn nhất, t[i-d..i+d] đối xứng
l, r = 0, -1 # hộp [l, r]: xâu đối xứng có đầu phải xa nhất
for i in range(m):
k = 0 if i > r else min(d[l + r - i], r - i) # soi gương qua tâm hộp
while i - k - 1 >= 0 and i + k + 1 < m and t[i - k - 1] == t[i + k + 1]:
k += 1
d[i] = k
if i + k > r:
l, r = i - k, i + k
best = max(d)
center = d.index(best)
start = (center - best) // 2 # d[i] chính là độ dài trong s
print(best)
print(s[start:start + best])Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$). Đếm số cặp $(l, r)$ với $1 \le l \le r \le |s|$ mà xâu con $s[l..r]$ đối xứng (hai xâu con giống nhau nhưng ở vị trí khác nhau được đếm riêng).
aaa6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
#. Cộng lại cho mọi $i$. Với aaa: 3 xâu a, 2 xâu aa, 1 xâu aaa. Đáp án có thể tới $5 \cdot 10^{11}$: dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
string t = "#";
for(char c : s){ t += c; t += '#'; }
int m = t.size();
vector<int> d(m, 0);
int l = 0, r = -1;
long long total = 0;
for(int i = 0; i < m; i++){
int k = (i > r) ? 0 : min(d[l + r - i], r - i);
while(i - k - 1 >= 0 && i + k + 1 < m && t[i - k - 1] == t[i + k + 1]) k++;
d[i] = k;
if(i + k > r){ l = i - k; r = i + k; }
total += (k + 1) / 2; // tâm i cho đúng (d[i] + 1) / 2 xâu đối xứng
}
cout << total;
return 0;
}import sys
s = sys.stdin.readline().strip()
t = '#' + '#'.join(s) + '#'
m = len(t)
d = [0] * m
l, r = 0, -1
total = 0
for i in range(m):
k = 0 if i > r else min(d[l + r - i], r - i)
while i - k - 1 >= 0 and i + k + 1 < m and t[i - k - 1] == t[i + k + 1]:
k += 1
d[i] = k
if i + k > r:
l, r = i - k, i + k
total += (k + 1) // 2 # tâm i cho đúng (d[i] + 1) // 2 xâu đối xứng
print(total)Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$). Hãy thêm ít ký tự nhất vào cuối $s$ để được một xâu đối xứng. Dòng 1 in số ký tự cần thêm, dòng 2 in xâu đối xứng thu được.
abcb1
abcba📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
# $+ s$ và tìm $j$ nhỏ nhất có $z = n - j$ tại vị trí ứng với $s[j]$. Với abcb: hậu tố bcb đối xứng, $j = 1$, thêm a. (Cũng làm được bằng Manacher: xâu đối xứng nào chạm cuối xâu và dài nhất.)Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n;
int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; }
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
string r(s.rbegin(), s.rend());
vector<int> z = zFunction(r + "#" + s);
int k = n - 1;
for(int j = 0; j < n; j++)
if(z[n + 1 + j] == n - j){ k = j; break; } // hậu tố s[j..] đối xứng
cout << k << "\n" << s + r.substr(n - k); // thêm đảo của s[0..k-1]
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
s = sys.stdin.readline().strip()
n = len(s)
r = s[::-1]
z = z_function(r + '#' + s)
k = n - 1
for j in range(n):
if z[n + 1 + j] == n - j: # hậu tố s[j:] đối xứng
k = j
break
print(k)
print(s + s[:k][::-1]) # thêm đảo của s[0..k-1]Cho văn bản $t$ và mẫu $p$ gồm chữ cái thường ($1 \le |p| \le |t| \le 10^6$). Tìm mọi vị trí $i$ (đánh số từ 1) sao cho đoạn $t[i..i + |p| - 1]$ khác $p$ ở không quá một vị trí. Dòng 1 in số lượng, dòng 2 in các vị trí tăng dần.
abcabdxbcaac
abc4
1 4 7 10📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
# + $t$), $suf$ = số ký tự cuối khớp liên tiếp với cuối $p$ (lấy từ $z$ của $p$ đảo + # + $t$ đảo, vị trí kết thúc $e = i + m - 1$ ứng với vị trí $n - 1 - e$ trong $t$ đảo). Đoạn sai không quá một ký tự khi và chỉ khi $pre + suf \ge m - 1$: phần khớp từ đầu và phần khớp từ cuối phủ kín mọi ô trừ tối đa một ô. Ví dụ: abc (khớp hẳn), abd, xbc, aac (mỗi đoạn sai 1 ký tự).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<int> zFunction(const string &s){
int n = s.size();
vector<int> z(n, 0);
if(n > 0) z[0] = n;
int l = 0, r = 0;
for(int i = 1; i < n; i++){
if(i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] - 1 > r){ l = i; r = i + z[i] - 1; }
}
return z;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string t, p;
cin >> t >> p;
int n = t.size(), m = p.size();
vector<int> z1 = zFunction(p + "#" + t); // tiền tố chung với p
string rp(p.rbegin(), p.rend()), rt(t.rbegin(), t.rend());
vector<int> z2 = zFunction(rp + "#" + rt); // hậu tố chung với p
vector<int> pos;
for(int i = 0; i + m <= n; i++){
int pre = z1[m + 1 + i]; // khớp từ đầu
int e = i + m - 1; // vị trí cuối của cửa sổ trong t
int suf = z2[m + 1 + (n - 1 - e)]; // khớp từ cuối
if(pre + suf >= m - 1) pos.push_back(i + 1);
}
cout << pos.size() << "\n";
for(int x : pos) cout << x << " ";
return 0;
}import sys
def z_function(s):
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
data = sys.stdin.read().split()
t, p = data[0], data[1]
n, m = len(t), len(p)
z1 = z_function(p + '#' + t) # tiền tố chung với p
z2 = z_function(p[::-1] + '#' + t[::-1]) # hậu tố chung với p
pos = []
for i in range(n - m + 1):
pre = z1[m + 1 + i]
e = i + m - 1 # vị trí cuối của cửa sổ trong t
suf = z2[m + 1 + (n - 1 - e)]
if pre + suf >= m - 1:
pos.append(i + 1)
print(len(pos))
print(*pos)Cho dãy $n$ số nguyên không âm ($n \le 10^5$, $a_i < 2^{30}$). Tìm giá trị lớn nhất của $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ với $1 \le l \le r \le n$.
5
8 1 2 12 715📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
1 2 12 có XOR $1 \oplus 2 \oplus 12 = 15$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
const int MAXNODE = (100005 + 1) * LOG + 5;
int nxt[MAXNODE][2], numNodes = 1;
void insertNum(int x){
int u = 0;
for(int b = LOG - 1; b >= 0; b--){
int c = (x >> b) & 1;
if(!nxt[u][c]) nxt[u][c] = numNodes++;
u = nxt[u][c];
}
}
int maxXor(int x){
int u = 0, res = 0;
for(int b = LOG - 1; b >= 0; b--){
int c = (x >> b) & 1;
if(nxt[u][c ^ 1]){ res |= 1 << b; u = nxt[u][c ^ 1]; }
else u = nxt[u][c];
}
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
int px = 0, best = 0;
insertNum(0); // tiền tố rỗng: px[0] = 0
for(int i = 0; i < n; i++){
int x;
cin >> x;
px ^= x; // px = a[1] ^ ... ^ a[i]
best = max(best, maxXor(px)); // đoạn (j, i] có XOR = px[i] ^ px[j]
insertNum(px);
}
cout << best;
return 0;
}import sys
LOG = 30
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c0, c1 = [0], [0] # con bit 0 / con bit 1 của mỗi nút
def insert(x):
u = 0
for b in range(LOG - 1, -1, -1):
if (x >> b) & 1:
if not c1[u]:
c1[u] = len(c0); c0.append(0); c1.append(0)
u = c1[u]
else:
if not c0[u]:
c0[u] = len(c0); c0.append(0); c1.append(0)
u = c0[u]
def max_xor(x):
u, res = 0, 0
for b in range(LOG - 1, -1, -1):
if (x >> b) & 1:
if c0[u]: res |= 1 << b; u = c0[u]
else: u = c1[u]
else:
if c1[u]: res |= 1 << b; u = c1[u]
else: u = c0[u]
return res
insert(0) # tiền tố rỗng
px = best = 0
for i in range(1, n + 1):
px ^= int(data[i])
best = max(best, max_xor(px)) # đoạn (j, i] có XOR = px[i] ^ px[j]
insert(px)
print(best)
main()Cho dãy $n$ số nguyên không âm ($n \le 10^5$, $a_i < 2^{30}$) và số $k$ ($1 \le k \le 2^{30}$). Đếm số cặp $(i, j)$ với $i < j$ và $a_i \oplus a_j < k$. Dòng 1 chứa $n$ và $k$, dòng 2 chứa dãy số.
5 3
1 2 3 4 53📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cnt ở mỗi nút (số số đi qua). Với số $x$, đi từ bit cao xuống và so bit của $x \oplus y$ với bit của $k$. Nếu bit của $k$ là 1: mọi $y$ ở nhánh cùng bit với $x$ cho bit XOR bằng 0 < 1, nên XOR chắc chắn nhỏ hơn $k$ → cộng ngay cnt của cả nhánh đó, rồi đi tiếp nhánh ngược bit (bit XOR = 1, vẫn đang bằng $k$). Nếu bit của $k$ là 0: bit XOR buộc phải bằng 0, đi nhánh cùng bit. Hết đường thì dừng; đi hết 31 bit nghĩa là XOR bằng $k$, không tính. Ba cặp ở ví dụ: $1 \oplus 3 = 2$, $2 \oplus 3 = 1$, $4 \oplus 5 = 1$. Dùng LOG = 31 vì $k$ có thể bằng $2^{30}$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int LOG = 31; // k có thể bằng 2^30
const int MAXNODE = 100005 * LOG + 5;
int nxt[MAXNODE][2], cnt[MAXNODE], numNodes = 1;
void insertNum(int x){
int u = 0;
for(int b = LOG - 1; b >= 0; b--){
int c = (x >> b) & 1;
if(!nxt[u][c]) nxt[u][c] = numNodes++;
u = nxt[u][c];
cnt[u]++; // số số đi qua nút u
}
}
long long countLess(int x, int k){ // số y trong trie có (x XOR y) < k
int u = 0;
long long res = 0;
for(int b = LOG - 1; b >= 0; b--){
int xb = (x >> b) & 1, kb = (k >> b) & 1;
if(kb == 1){
if(nxt[u][xb]) res += cnt[nxt[u][xb]]; // bit XOR = 0 < 1: cả nhánh đều nhỏ hơn k
u = nxt[u][xb ^ 1]; // bit XOR = 1 = bit của k: đi tiếp
} else {
u = nxt[u][xb]; // bit XOR bắt buộc = 0
}
if(!u) break; // hết đường
}
return res; // XOR đúng bằng k thì không tính
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
long long ans = 0;
for(int i = 0; i < n; i++){
int x;
cin >> x;
ans += countLess(x, k); // ghép x với các số đứng trước
insertNum(x);
}
cout << ans;
return 0;
}import sys
LOG = 31 # k có thể bằng 2^30
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
ch = [[0, 0]]
cnt = [0]
ans = 0
for i in range(n):
x = int(data[2 + i])
# đếm y đã có với (x XOR y) < k
u = 0
for b in range(LOG - 1, -1, -1):
xb = (x >> b) & 1
if (k >> b) & 1:
v = ch[u][xb]
if v:
ans += cnt[v] # bit XOR = 0 < 1: cả nhánh đều nhỏ hơn k
u = ch[u][xb ^ 1]
else:
u = ch[u][xb]
if not u:
break
# chèn x
u = 0
for b in range(LOG - 1, -1, -1):
c = (x >> b) & 1
if not ch[u][c]:
ch[u][c] = len(ch)
ch.append([0, 0]); cnt.append(0)
u = ch[u][c]
cnt[u] += 1
print(ans)
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét