Bài 28: Xử lý xâu nâng cao trong C++ và Python: Hash xâu và thuật toán KMP
Lời mở đầu
Ở bài 8 em đã làm quen với xâu ký tự: duyệt từng ký tự, đếm chữ cái, đảo xâu, hàm find có sẵn… Những thao tác ấy đủ dùng khi xâu ngắn. Nhưng đề HSG thường cho xâu dài $10^5$ tới $10^6$ ký tự và hỏi những câu như: mẫu $p$ xuất hiện bao nhiêu lần trong văn bản $t$? Hai đoạn con này có giống nhau không? Xâu con đối xứng dài nhất dài bao nhiêu? Làm “thật thà” thì mỗi câu tốn $O(n \cdot m)$ hoặc $O(n^2)$ và chắc chắn quá thời gian.
Bài này trang bị cho em hai vũ khí. Hash xâu biến mỗi xâu con thành một con số để so sánh trong $O(1)$; nó dùng lại phép toán modulo của bài 26 và kết hợp rất đẹp với tìm kiếm nhị phân ở bài 16. Thuật toán KMP với hàm tiền tố $\pi$ thì tìm mẫu chính xác tuyệt đối trong $O(n + m)$ và còn trả lời được nhiều câu hỏi về cấu trúc của xâu như chu kỳ, đường viền.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Bài toán tìm xâu mẫu và cách ngây thơ
Bài toán. Cho văn bản $t$ dài $n$ và mẫu $p$ dài $m$ ($m \le n$). Tìm mọi vị trí $i$ mà $p$ xuất hiện trong $t$ bắt đầu từ $i$, tức là $t[i..i+m-1] = p$. Các lần xuất hiện được phép chồng lên nhau: mẫu aba xuất hiện 2 lần trong ababa (tại vị trí 1 và 3, đánh số từ 1).
Cách ngây thơ: thử đặt mẫu ở từng vị trí $i = 0, 1, \ldots, n - m$, so lần lượt từng ký tự; gặp ký tự khác thì bỏ, sang vị trí kế tiếp.
Hình 1. Văn bản aaaaaaab, mẫu aaab. Ở mỗi vị trí, ba ký tự đầu đều khớp (xanh lá), tới ký tự thứ tư mới khác (đỏ). Ta so gần đủ $m$ ký tự cho mỗi vị trí.
Xem code C++ / Python: tìm mẫu ngây thơ $O(n \cdot m)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
string t, p;
cin >> t >> p;
int n = t.size(), m = p.size();
vector<int> pos;
for(int i = 0; i + m <= n; i++){ // đặt mẫu bắt đầu tại i
int k = 0;
while(k < m && t[i + k] == p[k]) k++; // so từng ký tự
if(k == m) pos.push_back(i + 1); // khớp hết m ký tự
}
cout << pos.size() << "\n";
for(int x : pos) cout << x << " ";
return 0;
}t = input().strip()
p = input().strip()
n, m = len(t), len(p)
pos = []
for i in range(n - m + 1): # đặt mẫu bắt đầu tại i
k = 0
while k < m and t[i + k] == p[k]: # so từng ký tự
k += 1
if k == m:
pos.append(i + 1)
print(len(pos))
print(' '.join(map(str, pos)))Vì sao chậm? Trường hợp xấu nhất như Hình 1: $t = $ aaa…a ($n$ chữ a), $p = $ aa…ab. Mỗi vị trí phải so gần đủ $m$ ký tự, tổng cộng khoảng $(n - m + 1) \cdot m$ phép so sánh. Với $n = 10^6, m = 5 \cdot 10^5$ con số đó là $2{,}5 \cdot 10^{11}$: chạy cả phút. Có hai điểm lãng phí:
- Mỗi lần thử, ta so sánh lại từ đầu cả m ký tự. Giá mà so sánh hai xâu dài $m$ chỉ tốn $O(1)$… → đó là ý tưởng của hash (phần 2, 3).
- Ở vị trí $i = 0$ ta đã biết
aaakhớp, thế mà sang $i = 1$ lại so lại chính những ký tự ấy. Giá mà nhớ được những gì đã khớp để không lùi lại… → đó là ý tưởng của KMP (phần 4, 5).
s.find(p) trong C++ và s.find(p), s.count(p) trong Python rất tiện, nhưng: find của C++ về bản chất là cách ngây thơ, có thể tốn $O(n \cdot m)$; count của Python đếm các lần xuất hiện không chồng nhau ("aaaa".count("aa") cho 2 chứ không phải 3). Dùng chúng cho bài dễ thì được, còn bài thi cần đếm chồng nhau hoặc dữ liệu “ác” thì phải tự cài.Phần 2Hash xâu đa thức
Ý tưởng. Đổi mỗi ký tự thành một số (ví dụ mã ASCII, hoặc a = 1, …, z = 26), rồi coi cả xâu là một số viết trong hệ cơ số $B$, giống như xâu chữ số "352" là số $3 \cdot 10^2 + 5 \cdot 10 + 2$. Số đó quá lớn nên ta lấy dư cho một số nguyên tố $M$:
$\text{hash}(s) = \left(s_0 \cdot B^{k-1} + s_1 \cdot B^{k-2} + \cdots + s_{k-1} \cdot B^0\right) \bmod M$
Hai xâu bằng nhau thì chắc chắn có hash bằng nhau. Chiều ngược lại “gần như” đúng: hash bằng nhau thì xâu bằng nhau với xác suất rất cao nếu $M$ đủ lớn. So sánh hai số chỉ tốn $O(1)$, dù xâu dài bao nhiêu.
Hash tiền tố. Gọi $h_i$ là hash của $i$ ký tự đầu ($h_0 = 0$). Thêm một ký tự vào cuối giống như viết thêm một chữ số: nhân với $B$ rồi cộng. Đồng thời chuẩn bị luôn mảng lũy thừa $p_i = B^i \bmod M$:
$h_{i+1} = (h_i \cdot B + s_i) \bmod M, \qquad p_{i+1} = p_i \cdot B \bmod M$
Hash xâu con trong $O(1)$. Xâu con $s[l..r-1]$ (dài $r - l$) có hash bằng
$\text{get}(l, r) = (h_r - h_l \cdot p_{r-l}) \bmod M$
Vì sao? $h_r$ là “số” viết bởi $r$ ký tự đầu. Phần $l$ ký tự đầu đóng góp $h_l$ nhưng đã bị đẩy sang trái thêm $r - l$ chữ số, tức là bị nhân $B^{r-l}$. Trừ phần đó đi, còn lại đúng phần của $s[l..r-1]$. Hệt như với số thập phân: từ $35217$ muốn lấy $217$ thì làm $35217 - 35 \cdot 10^3$.
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| s[i − 1] | – | a | b | c | a | b |
| h[i] | 0 | 1 | 33 | 17 | 528 | 226 |
| p[i] = 31i mod 1009 | 1 | 31 | 961 | 530 | 286 | 794 |
Bảng 1. Hash tiền tố của abcab với $B = 31$, $M = 1009$, a = 1, b = 2, c = 3. Hai xâu con ab = s[0..1] và s[3..4]: get(0, 2) = (33 − 0 · 961) mod 1009 = 33, get(3, 5) = (226 − 17 · 961) mod 1009 = 33. Bằng nhau, đúng như mong đợi.
Em tự nhập xâu của mình vào mô phỏng dưới đây để xem từng giá trị $h_i$, $p_i$ được tính ra sao và hash xâu con lấy từ đâu. Thử xâu aaacdd, vị trí 0 và 3, độ dài 3: hai xâu aaa và cdd khác nhau mà hash lại bằng nhau. Đó là va chạm, lý do không bao giờ dùng $M$ nhỏ khi code thật.
Chọn $B$ và $M$ thế nào? $B$ nên lớn hơn số loại ký tự (với mã ASCII, chọn $B = 131$ hoặc một số ngẫu nhiên lớn). $M$ phải là số nguyên tố rất lớn. Lựa chọn tốt nhất hiện nay là $M = 2^{61} - 1$ (một số nguyên tố Mersenne): tích hai số nhỏ hơn $M$ vượt quá unsigned long long, nên trong C++ ta nhân qua kiểu __int128; Python thì có số nguyên lớn sẵn, cứ nhân rồi % bình thường.
Xem code C++ / Python: so sánh hai xâu con bằng hash, mỗi truy vấn $O(1)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1; // số nguyên tố Mersenne 2^61 - 1
const ull BASE = 131;
vector<ull> h, pw;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
ull getHash(int l, int r){ // hash của s[l..r-1], O(1)
return (h[r] + MOD - mulmod(h[l], pw[r - l])) % MOD;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
int q;
cin >> s >> q;
int n = s.size();
h.assign(n + 1, 0); pw.assign(n + 1, 1);
for(int i = 0; i < n; i++){
h[i + 1] = (mulmod(h[i], BASE) + s[i]) % MOD; // hash tiền tố
pw[i + 1] = mulmod(pw[i], BASE); // BASE^(i+1)
}
while(q--){
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2; // đánh số từ 1, đoạn đóng
bool ok = (r1 - l1 == r2 - l2) && getHash(l1 - 1, r1) == getHash(l2 - 1, r2);
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}import sys
MOD = (1 << 61) - 1 # số nguyên tố Mersenne 2^61 - 1
BASE = 131
data = sys.stdin.buffer.read().split()
s = data[0] # bytes: s[i] là mã ASCII
q = int(data[1])
n = len(s)
h = [0] * (n + 1)
pw = [1] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * BASE + s[i]) % MOD # hash tiền tố
pw[i + 1] = pw[i] * BASE % MOD # BASE^(i+1)
def get(l, r): # hash của s[l..r-1], O(1)
return (h[r] - h[l] * pw[r - l]) % MOD
out = []
for k in range(q):
l1, r1, l2, r2 = map(int, data[2 + 4 * k: 6 + 4 * k])
ok = r1 - l1 == r2 - l2 and get(l1 - 1, r1) == get(l2 - 1, r2)
out.append("YES" if ok else "NO")
print("\n".join(out))h[0] = 0; pw[0] = 1;
for(int i = 0; i < n; i++){
h[i + 1] = (h[i] * BASE + s[i]) % MOD; // hash tiền tố
pw[i + 1] = pw[i] * BASE % MOD; // BASE^(i+1)
}
// hash của s[l..r-1]
get(l, r) = (h[r] - h[l] * pw[r - l] % MOD + MOD) % MOD;__int128 như hàm mulmod ở trên.set để đếm hay tìm trùng, có tới $\approx 5 \cdot 10^9$ cặp; theo nghịch lý ngày sinh, chỉ cần khoảng $\sqrt{M} \approx 3 \cdot 10^4$ xâu là đã dễ có hai xâu khác nhau trùng hash với $M \approx 10^9$. Cách phòng: dùng $M = 2^{61} - 1$ (xác suất va chạm cỡ $n^2 / 2^{61}$, cực nhỏ), hoặc hash kép: tính song song hai hash với hai modulo khác nhau (ví dụ $10^9 + 7$ và $998244353$) và chỉ coi là bằng nhau khi cả hai cặp đều bằng. Ngoài ra đừng dùng unsigned long long tràn số tự nhiên (modulo $2^{64}$) làm hash: có dãy xâu Thue–Morse cố tình làm nó va chạm.Phần 3Ứng dụng của hash
1. Tìm mẫu (Rabin–Karp). Tính hash của mẫu $p$ một lần. Rồi với mỗi vị trí $i$, lấy hash của $t[i..i+m-1]$ trong $O(1)$ và so với hash mẫu. Tổng thời gian $O(n + m)$. Đoạn code ngắn và dễ nhớ, dùng tốt khi đi thi; nhược điểm duy nhất là có xác suất (rất nhỏ) báo nhầm do va chạm.
Xem code C++ / Python: tìm mẫu bằng hash (Rabin–Karp) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1, BASE = 131;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string t, p;
cin >> t >> p;
int n = t.size(), m = p.size();
vector<ull> h(n + 1, 0), pw(n + 1, 1);
for(int i = 0; i < n; i++){
h[i + 1] = (mulmod(h[i], BASE) + t[i]) % MOD;
pw[i + 1] = mulmod(pw[i], BASE);
}
ull hp = 0; // hash của cả mẫu p
for(char c : p) hp = (mulmod(hp, BASE) + c) % MOD;
vector<int> pos;
for(int i = 0; i + m <= n; i++){
ull cur = (h[i + m] + MOD - mulmod(h[i], pw[m])) % MOD; // hash t[i..i+m-1]
if(cur == hp) pos.push_back(i + 1);
}
cout << pos.size() << "\n";
for(int x : pos) cout << x << " ";
return 0;
}import sys
MOD, BASE = (1 << 61) - 1, 131
data = sys.stdin.buffer.read().split()
t, p = data[0], data[1]
n, m = len(t), len(p)
h = [0] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * BASE + t[i]) % MOD
hp = 0 # hash của cả mẫu p
for c in p:
hp = (hp * BASE + c) % MOD
pm = pow(BASE, m, MOD)
# zip(h[m:], h) cho từng cặp (h[i + m], h[i]): nhanh hơn truy cập chỉ số
pos = [i + 1 for i, (x, y) in enumerate(zip(h[m:], h)) if (x - y * pm) % MOD == hp]
print(len(pos))
print(' '.join(map(str, pos)))2. Xâu con chung dài nhất của hai xâu. Cho hai xâu $a$, $b$ (dài tới $10^5$). Tìm độ dài lớn nhất của một xâu xuất hiện liên tiếp trong cả hai. Quy hoạch động $O(n \cdot m)$ quá chậm. Nhận xét then chốt: nếu có xâu con chung độ dài $L$ thì cũng có xâu con chung độ dài $L - 1$ (bỏ ký tự cuối đi). Tính chất “đúng tới một ngưỡng rồi sai mãi” này chính là điều kiện để chặt nhị phân theo đáp án.
Với mỗi $L$ cần kiểm tra: lấy hash mọi xâu con độ dài $L$ của $a$ cho vào một tập hợp (hoặc mảng đã sắp xếp), rồi xem có xâu con độ dài $L$ nào của $b$ có hash nằm trong tập đó. Mỗi lần kiểm tra $O(n + m)$ (hoặc thêm $\log$ nếu sắp xếp), chặt nhị phân $\log$ lần, tổng $O((n + m) \log n)$.
| L | xâu con độ dài L của a = xabcdy | của b = zbcdabw có trong đó? | check(L) |
|---|---|---|---|
| 2 | xa, ab, bc, cd, dy | bc, cd, ab có | đúng |
| 3 | xab, abc, bcd, cdy | bcd có | đúng |
| 4 | xabc, abcd, bcdy | zbcd, bcda, cdab, dabw: không | sai |
Bảng 2. Chặt nhị phân trên độ dài L. check(3) đúng, check(4) sai nên đáp án là 3 (xâu chung bcd). Thực tế ta so các hash chứ không so xâu.
Xem code C++ / Python: xâu con chung dài nhất bằng chặt nhị phân + hash (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1, BASE = 131;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
vector<ull> pw;
vector<ull> build(const string &s){
vector<ull> h(s.size() + 1, 0);
for(int i = 0; i < (int)s.size(); i++) h[i + 1] = (mulmod(h[i], BASE) + s[i]) % MOD;
return h;
}
ull get(const vector<ull> &h, int l, int len){
return (h[l + len] + MOD - mulmod(h[l], pw[len])) % MOD;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
pw.assign(max(n, m) + 1, 1);
for(int i = 1; i <= max(n, m); i++) pw[i] = mulmod(pw[i - 1], BASE);
vector<ull> ha = build(a), hb = build(b);
auto check = [&](int L){ // có xâu con chung độ dài L không?
vector<ull> v;
for(int i = 0; i + L <= n; i++) v.push_back(get(ha, i, L));
sort(v.begin(), v.end());
for(int i = 0; i + L <= m; i++)
if(binary_search(v.begin(), v.end(), get(hb, i, L))) return true;
return false;
};
int lo = 0, hi = min(n, m); // check(lo) luôn đúng
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(check(mid)) lo = mid; else hi = mid - 1;
}
cout << lo;
return 0;
}import sys
MOD, BASE = (1 << 61) - 1, 131
data = sys.stdin.buffer.read().split()
a, b = data[0], data[1]
n, m = len(a), len(b)
def build(s):
h = [0] * (len(s) + 1)
for i, c in enumerate(s):
h[i + 1] = (h[i] * BASE + c) % MOD
return h
ha, hb = build(a), build(b)
def check(L): # có xâu con chung độ dài L không?
pL = pow(BASE, L, MOD)
seen = {(x - y * pL) % MOD for x, y in zip(ha[L:], ha)} # cặp (ha[i + L], ha[i])
return not seen.isdisjoint([(x - y * pL) % MOD for x, y in zip(hb[L:], hb)])
lo, hi = 0, min(n, m) # check(lo) luôn đúng
while lo < hi:
mid = (lo + hi + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
print(lo)3. Đếm xâu con phân biệt độ dài $k$. Lấy hash của tất cả $n - k + 1$ xâu con độ dài $k$, đếm số giá trị khác nhau (cho vào set, hoặc sắp xếp rồi unique). Thời gian $O(n \log n)$, trong khi nếu cho từng xâu con vào set<string> thì tốn $O(n \cdot k)$ bộ nhớ và thời gian. Đây là bài tập 6.
4. Kiểm tra đối xứng. Tính thêm hash tiền tố của xâu đảo $r$. Xâu con $s[l..r-1]$ đối xứng khi và chỉ khi hash của nó bằng hash của đoạn tương ứng trên $r$. Kết hợp với chặt nhị phân sẽ tìm được xâu con đối xứng dài nhất (bài tập 7).
Phần 4Hàm tiền tố và thuật toán KMP
Hash nhanh và dễ code nhưng có xác suất sai. Thuật toán KMP (Knuth–Morris–Pratt) thì tìm mẫu chính xác tuyệt đối trong $O(n + m)$. Trái tim của nó là hàm tiền tố.
Định nghĩa. Một đường viền của xâu là một xâu vừa là tiền tố, vừa là hậu tố của nó, và ngắn hơn chính nó. Ví dụ abacaba có các đường viền a và aba. Hàm tiền tố của xâu $s$ là mảng $\pi$ với
$\pi[i]$ = độ dài đường viền dài nhất của tiền tố $s[0..i]$.
Hình 2. aba vừa là tiền tố (xanh dương) vừa là hậu tố (xanh lá) của abacaba, và là đường viền dài nhất, nên $\pi[6] = 3$.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| s[i] | a | b | a | c | a | b | a | b | c |
| π[i] | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 2 | 0 |
| đường viền | – | – | a | – | a | ab | aba | ab | – |
Bảng 3. Hàm tiền tố của abacababc. Ví dụ $\pi[7] = 2$: tiền tố abacabab có đường viền dài nhất là ab.
Tính $\pi$ trong $O(n)$. Giả sử đã có $\pi[0..i-1]$, cần tính $\pi[i]$. Đặt $j = \pi[i-1]$: đoạn $s[0..j-1]$ đang khớp với đoạn kết thúc tại $i - 1$.
- Nếu $s[i] = s[j]$: đường viền nối dài được thêm 1 ký tự, $\pi[i] = j + 1$.
- Nếu $s[i] \ne s[j]$: phải thử đường viền ngắn hơn. Đường viền dài nhất tiếp theo của $s[0..i-1]$ chính là đường viền dài nhất của $s[0..j-1]$, tức là $\pi[j-1]$. Gán $j = \pi[j-1]$ rồi thử lại. Lùi tới khi khớp hoặc $j = 0$.
Vì sao lại là $\pi[j-1]$? Đoạn đang khớp là $s[0..j-1]$, nó xuất hiện cả ở đầu xâu lẫn ngay trước $i$. Một đường viền ngắn hơn của $s[0..i-1]$ phải vừa là tiền tố vừa là hậu tố của chính đoạn $s[0..j-1]$ đó, và dài nhất trong số ấy có độ dài $\pi[j-1]$, đã tính sẵn. Em xem mô phỏng, chú ý lúc dòng “tiền tố” nhảy sang phải nhiều ô một lúc:
Vì sao $O(n)$ dù có vòng while lồng trong for? Mỗi bước $i$, $j$ tăng tối đa 1. Mỗi lần lùi, $j$ giảm ít nhất 1 và $j$ không bao giờ âm. Vậy tổng số lần lùi không vượt quá tổng số lần tăng, tức là không quá $n$. Cả thuật toán tốn $O(n)$.
Thuật toán KMP. Tìm $p$ trong $t$ bằng đúng ý tưởng đó: duyệt $i$ trên $t$, giữ $j$ là số ký tự đầu của $p$ đang khớp với đoạn kết thúc tại $t[i-1]$. Khớp thì tăng $j$; khác thì lùi $j = \pi[j-1]$ (dùng $\pi$ của mẫu), tương đương với việc trượt mẫu sang phải $j - \pi[j-1]$ ô một lúc mà không bỏ sót vị trí nào. Khi $j = m$: tìm thấy một lần xuất hiện kết thúc tại $i$, rồi đặt $j = \pi[m-1]$ để tìm tiếp. Con trỏ $i$ không bao giờ lùi, tổng thời gian $O(n + m)$.
Xem code C++ / Python: thuật toán KMP tìm mọi vị trí xuất hiện $O(n + m)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
vector<int> prefixFunction(const string &s){
int n = s.size();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1]; // lùi theo đường viền
if(s[i] == s[j]) j++; // nối dài được
pi[i] = j;
}
return pi;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string t, p;
cin >> t >> p;
vector<int> pi = prefixFunction(p);
int n = t.size(), m = p.size(), j = 0; // j: số ký tự đầu của p đang khớp
vector<int> pos;
for(int i = 0; i < n; i++){ // i không bao giờ lùi
while(j > 0 && t[i] != p[j]) j = pi[j - 1];
if(t[i] == p[j]) j++;
if(j == m){
pos.push_back(i - m + 2); // vị trí bắt đầu, đánh số từ 1
j = pi[j - 1];
}
}
cout << pos.size() << "\n";
for(int x : pos) cout << x << " ";
return 0;
}import sys
def prefix_function(s):
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
c = s[i]
while j and c != s[j]: # lùi theo đường viền
j = pi[j - 1]
if c == s[j]: # nối dài được
j += 1
pi[i] = j
return pi
data = sys.stdin.buffer.read().split()
t, p = data[0], data[1]
pi = prefix_function(p)
m, j, pos = len(p), 0, []
for i, c in enumerate(t): # i không bao giờ lùi
while j and c != p[j]:
j = pi[j - 1]
if c == p[j]:
j += 1
if j == m:
pos.append(i - m + 2) # vị trí bắt đầu, đánh số từ 1
j = pi[j - 1]
print(len(pos))
print(' '.join(map(str, pos)))# $+ t$, với # là ký tự không có trong cả hai. Vì # chặn lại, $\pi$ không bao giờ vượt $m$; vị trí $i$ có $\pi[i] = m$ chính là chỗ mẫu kết thúc trong $t$ (bắt đầu tại $i - 2m$ nếu đánh số từ 0 trong $t$). Bài tập 2 dùng mẹo này.j = pi[j] thay vì j = pi[j - 1]. 2. Quên đặt j = pi[j - 1] sau khi tìm thấy, làm truy cập p[m] ngoài mảng. 3. Dùng $\pi$ của văn bản thay vì của mẫu. 4. Trong Python, viết while j > 0 and ... trên str vẫn đúng, nhưng đọc dữ liệu bằng sys.stdin.buffer (so sánh số nguyên của bytes) sẽ nhanh hơn rõ rệt.Phần 5Ứng dụng của hàm tiền tố
1. Chu kỳ nhỏ nhất của xâu. Số $k$ gọi là chu kỳ của $s$ nếu $s[i] = s[i + k]$ với mọi $i$ hợp lệ. Nhận xét: $s$ có đường viền độ dài $L$ khi và chỉ khi $s$ có chu kỳ $n - L$ (dịch xâu sang phải $n - L$ ô thì phần chồng lên nhau khớp). Đường viền dài nhất cho chu kỳ nhỏ nhất:
$k = n - \pi[n-1]$
Nếu thêm điều kiện $k$ chia hết $n$ thì $s$ là $n / k$ bản sao ghép lại của $s[0..k-1]$; ngược lại $s$ không viết được thành các bản sao của xâu ngắn hơn.
Hình 3. $s$ = abcabcabc, $\pi[8] = 6$ (đường viền abcabc). Dịch sang phải $9 - 6 = 3$ ô, phần chồng lên (xanh lá) khớp hoàn toàn: chu kỳ nhỏ nhất là 3, và 3 chia hết 9 nên $s$ = abc × 3.
2. Đếm số lần xuất hiện của mọi tiền tố. Với mỗi $L = 1..n$, tiền tố độ dài $L$ xuất hiện bao nhiêu lần trong $s$? Tiền tố độ dài $L$ xuất hiện kết thúc tại vị trí $i$ khi và chỉ khi $L$ là một đường viền của $s[0..i]$ (hoặc chính là $s[0..i]$). Các đường viền của $s[0..i]$ là dãy $\pi[i], \pi[\pi[i]-1], \ldots$ Vì vậy: đếm $\text{cnt}[\pi[i]]$ với mọi $i$, rồi đi $L$ từ lớn xuống nhỏ, cộng $\text{cnt}[L]$ vào $\text{cnt}[\pi[L-1]]$, cuối cùng cộng 1 cho lần xuất hiện ở chính đầu xâu. Tổng $O(n)$.
Xem code C++ / Python: đếm số lần xuất hiện của mọi tiền tố (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
}
vector<long long> cnt(n + 1, 0);
for(int i = 0; i < n; i++) cnt[pi[i]]++; // đường viền dài nhất tại i
for(int L = n; L >= 1; L--) cnt[pi[L - 1]] += cnt[L]; // truyền xuống các đường viền ngắn hơn
for(int L = 1; L <= n; L++) cout << cnt[L] + 1 << " "; // +1: chính tiền tố đó
return 0;
}import sys
s = sys.stdin.buffer.readline().strip()
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
c = s[i]
while j and c != s[j]:
j = pi[j - 1]
if c == s[j]:
j += 1
pi[i] = j
cnt = [0] * (n + 1)
for v in pi: # đường viền dài nhất tại mỗi vị trí
cnt[v] += 1
for L in range(n, 0, -1): # truyền xuống các đường viền ngắn hơn
cnt[pi[L - 1]] += cnt[L]
print(' '.join(str(c + 1) for c in cnt[1:])) # +1: chính tiền tố đó3. Liệt kê mọi đường viền (tiền tố đồng thời là hậu tố): đi theo dãy $n \to \pi[n-1] \to \pi[\pi[n-1]-1] \to \cdots \to 0$ (bài tập 4). 4. Xoay vòng: $b$ là một phép xoay của $a$ khi và chỉ khi $b$ xuất hiện trong $a + a$ (bài tập 5).
| Tiêu chí | Hash xâu | KMP / hàm tiền tố |
|---|---|---|
| Tìm mọi vị trí của mẫu | $O(n + m)$ | $O(n + m)$ |
| Độ chính xác | sai với xác suất rất nhỏ (va chạm) | chính xác tuyệt đối |
| So sánh hai xâu con bất kỳ | $O(1)$ sau khi chuẩn bị | không làm được trực tiếp |
| Kết hợp chặt nhị phân, set, map | rất tự nhiên | khó |
| Chu kỳ, đường viền, tiền tố lặp | được nhưng vòng vèo | trả lời ngay từ $\pi$ |
| Độ dài code | ngắn | ngắn |
| Lỗi hay gặp | M nhỏ, quên + M khi trừ, tràn số | lệch chỉ số $\pi[j-1]$ |
Bảng 4. Hash hay KMP? Khi chỉ cần tìm một mẫu cố định, KMP an toàn hơn. Khi cần so sánh nhiều xâu con khác nhau, hash gần như là lựa chọn duy nhất ở mức HSG.
# $+ t$, chu kỳ, đếm tiền tố…). Ví dụ $z$ của aabxaab là [–, 1, 0, 0, 3, 1, 0]. Em chỉ cần thành thạo một trong hai; bài này chọn hàm tiền tố vì nó là nền của KMP và của automaton KMP sau này.- Xâu Duy Nhất (Xauduynhat) (Trung bình)
- Chuỗi hạt bồ đề (PTIT009) (Trung bình)
- Biến đổi xâu đối xứng (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á)
- Palindrome Kép (Khó)
Bài tậpLuyện hash và KMP
Cho văn bản $t$ và mẫu $p$ gồm các chữ cái Latin thường ($1 \le |p| \le |t| \le 10^6$), mỗi xâu trên một dòng. Đếm số vị trí mà $p$ xuất hiện trong $t$ (các lần xuất hiện được phép chồng lên nhau).
aaaa
aa3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
aa xuất hiện tại vị trí 1, 2, 3. Chú ý "aaaa".count("aa") của Python trả về 2 vì nó không đếm chồng nhau.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 t, p;
cin >> t >> p;
int m = p.size();
vector<int> pi(m, 0);
for(int i = 1; i < m; i++){
int j = pi[i - 1];
while(j > 0 && p[i] != p[j]) j = pi[j - 1];
if(p[i] == p[j]) j++;
pi[i] = j;
}
long long cnt = 0;
int j = 0;
for(char c : t){
while(j > 0 && c != p[j]) j = pi[j - 1];
if(c == p[j]) j++;
if(j == m){ cnt++; j = pi[j - 1]; }
}
cout << cnt;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
t, p = data[0], data[1]
m = len(p)
pi = [0] * m
j = 0
for i in range(1, m):
c = p[i]
while j and c != p[j]:
j = pi[j - 1]
if c == p[j]:
j += 1
pi[i] = j
cnt = j = 0
for c in t:
while j and c != p[j]:
j = pi[j - 1]
if c == p[j]:
j += 1
if j == m:
cnt += 1
j = pi[j - 1]
print(cnt)Cho văn bản $t$ và mẫu $p$ gồm các chữ cái Latin thường ($1 \le |p| \le |t| \le 10^6$). In ra vị trí (đánh số từ 1) của lần xuất hiện đầu tiên của $p$ trong $t$, hoặc $-1$ nếu không có. Hãy giải bằng mẹo nối xâu $p + $ # $+ t$.
xyabcabd
abd6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abd#xyabcabd. Vị trí đầu tiên có $\pi[i] = m = 3$ là $i = 11$; trừ đi $m + 1$ ký tự của phần abd# được chỉ số kết thúc trong $t$ là 7 (từ 0), vị trí bắt đầu là $7 - 3 + 1 = 5$ (từ 0), tức là 6 nếu đánh số từ 1. Gộp lại: đáp án $= i - 2m + 1$. Gặp là dừng luôn, không cần tính tiếp.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 t, p;
cin >> t >> p;
int m = p.size();
string s = p + "#" + t; // '#' không có trong t, p
int n = s.size();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
if(j == m){ // p kết thúc tại vị trí i của s
cout << i - 2 * m + 1; // đổi về vị trí bắt đầu trong t (từ 1)
return 0;
}
}
cout << -1;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
t, p = data[0], data[1]
m = len(p)
s = p + b"#" + t # '#' không có trong t, p
n = len(s)
pi = [0] * n
j = 0
ans = -1
for i in range(1, n):
c = s[i]
while j and c != s[j]:
j = pi[j - 1]
if c == s[j]:
j += 1
pi[i] = j
if j == m: # p kết thúc tại vị trí i của s
ans = i - 2 * m + 1 # đổi về vị trí bắt đầu trong t (từ 1)
break
print(ans)Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$). Tìm độ dài $k$ nhỏ nhất sao cho $s$ bằng một số bản sao của $s[0..k-1]$ ghép liên tiếp (nếu không có thì $k = |s|$).
abcabcabc3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abcabcabc: $\pi[8] = 6$, $k = 3$ chia hết 9. Với abcab: $\pi[4] = 2$, $k = 3$ không chia hết 5 nên đáp án là 5. (Có thể chứng minh: nếu có một chu kỳ chia hết $n$ thì chu kỳ nhỏ nhất cũng chia hết $n$.)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;
int n = s.size();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
}
int k = n - pi[n - 1]; // chu kỳ nhỏ nhất
cout << (n % k == 0 ? k : n);
return 0;
}import sys
s = sys.stdin.buffer.readline().strip()
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
c = s[i]
while j and c != s[j]:
j = pi[j - 1]
if c == s[j]:
j += 1
pi[i] = j
k = n - pi[n - 1] # chu kỳ nhỏ nhất
print(k if n % k == 0 else n)Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^6$). Tìm mọi độ dài $L$ ($1 \le L \le |s|$) sao cho tiền tố độ dài $L$ bằng hậu tố độ dài $L$. Dòng 1 in số lượng, dòng 2 in các độ dài theo thứ tự tăng dần.
abacaba3
1 3 7📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abacaba: $7 \to \pi[6] = 3 \to \pi[2] = 1 \to \pi[0] = 0$, dừng. Đảo lại được 1 3 7.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;
int n = s.size();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
}
vector<int> res;
for(int L = n; L > 0; L = pi[L - 1]) res.push_back(L); // n, π[n-1], π[π[n-1]-1], ...
reverse(res.begin(), res.end());
cout << res.size() << "\n";
for(int x : res) cout << x << " ";
return 0;
}import sys
s = sys.stdin.buffer.readline().strip()
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
c = s[i]
while j and c != s[j]:
j = pi[j - 1]
if c == s[j]:
j += 1
pi[i] = j
res = []
L = n
while L > 0: # n, π[n-1], π[π[n-1]-1], ...
res.append(L)
L = pi[L - 1]
res.reverse()
print(len(res))
print(' '.join(map(str, res)))Cho hai xâu $a$, $b$ cùng độ dài $n$ ($1 \le n \le 10^6$), gồm chữ cái thường. Một phép xoay $k$ bước chuyển $k$ ký tự đầu của $a$ xuống cuối. Tìm $k$ nhỏ nhất ($0 \le k < n$) sao cho xoay $a$ đi $k$ bước được $b$, hoặc in $-1$ nếu không có.
abcde
cdeab2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
abcde + abcd = abcdeabcd, cdeab bắt đầu ở vị trí 2.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 a, b;
cin >> a >> b;
int n = a.size();
string t = a + a.substr(0, n - 1); // mọi phép xoay của a đều là xâu con độ dài n của t
vector<int> pi(n, 0); // hàm tiền tố của b
for(int i = 1; i < n; i++){
int j = pi[i - 1];
while(j > 0 && b[i] != b[j]) j = pi[j - 1];
if(b[i] == b[j]) j++;
pi[i] = j;
}
int j = 0;
for(int i = 0; i < (int)t.size(); i++){
while(j > 0 && t[i] != b[j]) j = pi[j - 1];
if(t[i] == b[j]) j++;
if(j == n){ cout << i - n + 1; return 0; } // lần xuất hiện đầu tiên
}
cout << -1;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
a, b = data[0], data[1]
n = len(a)
t = a + a[:n - 1] # mọi phép xoay của a đều là xâu con độ dài n của t
pi = [0] * n # hàm tiền tố của b
j = 0
for i in range(1, n):
c = b[i]
while j and c != b[j]:
j = pi[j - 1]
if c == b[j]:
j += 1
pi[i] = j
ans, j = -1, 0
for i, c in enumerate(t):
while j and c != b[j]:
j = pi[j - 1]
if c == b[j]:
j += 1
if j == n:
ans = i - n + 1 # lần xuất hiện đầu tiên
break
print(ans)Cho xâu $s$ độ dài $n$ gồm chữ cái thường và số $k$ ($1 \le k \le n \le 2 \cdot 10^5$). Đếm số xâu khác nhau có độ dài đúng $k$ xuất hiện liên tiếp trong $s$. Dòng 1 chứa $n$ và $k$, dòng 2 chứa $s$.
7 2
abababc3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
ab, ba, bc.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1, BASE = 131;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
string s;
cin >> n >> k >> s;
vector<ull> h(n + 1, 0);
for(int i = 0; i < n; i++) h[i + 1] = (mulmod(h[i], BASE) + s[i]) % MOD;
ull pk = 1;
for(int i = 0; i < k; i++) pk = mulmod(pk, BASE);
vector<ull> v;
for(int i = 0; i + k <= n; i++) v.push_back((h[i + k] + MOD - mulmod(h[i], pk)) % MOD);
sort(v.begin(), v.end());
cout << unique(v.begin(), v.end()) - v.begin(); // số hash khác nhau
return 0;
}import sys
MOD, BASE = (1 << 61) - 1, 131
data = sys.stdin.buffer.read().split()
n, k, s = int(data[0]), int(data[1]), data[2]
h = [0] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * BASE + s[i]) % MOD
pk = pow(BASE, k, MOD)
print(len({(x - y * pk) % MOD for x, y in zip(h[k:], h)})) # cặp (h[i + k], h[i])Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^5$). Tìm độ dài của xâu con liên tiếp đối xứng (đọc xuôi, ngược như nhau) dài nhất. Hãy giải bằng hash và chặt nhị phân.
cabbadac4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
aba chưa chắc có xâu đối xứng dài 2). Kiểm tra $s[i..i+L-1]$ đối xứng: so hash của nó với hash của đoạn tương ứng trên xâu đảo $r$, đó là $r[n-i-L..n-i-1]$. Với cabbadac: dài nhất là abba (độ dài 4); ada chỉ dài 3.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1, BASE = 131;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
int n;
vector<ull> h, g, pw; // h: hash của s, g: hash của xâu đảo r
ull get(const vector<ull> &x, int l, int len){
return (x[l + len] + MOD - mulmod(x[l], pw[len])) % MOD;
}
bool check(int L){ // có xâu con đối xứng độ dài L không?
for(int i = 0; i + L <= n; i++)
if(get(h, i, L) == get(g, n - i - L, L)) return true; // s[i..i+L-1] đảo ngược = chính nó
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
n = s.size();
string r(s.rbegin(), s.rend());
h.assign(n + 1, 0); g.assign(n + 1, 0); pw.assign(n + 1, 1);
for(int i = 0; i < n; i++){
h[i + 1] = (mulmod(h[i], BASE) + s[i]) % MOD;
g[i + 1] = (mulmod(g[i], BASE) + r[i]) % MOD;
pw[i + 1] = mulmod(pw[i], BASE);
}
int lo = 0, hi = (n - 1) / 2; // độ dài lẻ 2k + 1
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(check(2 * mid + 1)) lo = mid; else hi = mid - 1;
}
int best = 2 * lo + 1;
lo = 0; hi = n / 2; // độ dài chẵn 2k
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(check(2 * mid)) lo = mid; else hi = mid - 1;
}
cout << max(best, 2 * lo);
return 0;
}import sys
MOD, BASE = (1 << 61) - 1, 131
s = sys.stdin.buffer.readline().strip()
n = len(s)
r = s[::-1]
h = [0] * (n + 1) # hash của s
g = [0] * (n + 1) # hash của xâu đảo r
for i in range(n):
h[i + 1] = (h[i] * BASE + s[i]) % MOD
g[i + 1] = (g[i] * BASE + r[i]) % MOD
def check(L): # có xâu con đối xứng độ dài L không?
pL = pow(BASE, L, MOD)
A = [(x - y * pL) % MOD for x, y in zip(h[L:], h)] # A[i]: hash s[i..i+L-1]
G = [(x - y * pL) % MOD for x, y in zip(g[L:], g)] # G[j]: hash r[j..j+L-1]
# s[i..i+L-1] đảo ngược chính là r[n-i-L..n-i-1], tức G[n - L - i]
return any(x == y for x, y in zip(A, reversed(G)))
def search(lo, hi, f): # k lớn nhất trong [lo, hi] có check(f(k))
while lo < hi:
mid = (lo + hi + 1) // 2
if check(f(mid)):
lo = mid
else:
hi = mid - 1
return f(lo)
odd = search(0, (n - 1) // 2, lambda k: 2 * k + 1)
even = search(0, n // 2, lambda k: 2 * k)
print(max(odd, even))Cho xâu $s$ gồm chữ cái thường ($1 \le |s| \le 10^5$). Tìm độ dài lớn nhất của một xâu xuất hiện liên tiếp ít nhất hai lần trong $s$ (hai lần xuất hiện được phép chồng lên nhau). In 0 nếu không có.
banana3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
set nhỏ hơn số xâu con, hoặc sắp xếp rồi xem hai phần tử kề nhau). ana xuất hiện ở vị trí 2 và 4 (chồng lên nhau), còn không có xâu dài 4 nào lặp lại.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1, BASE = 131;
ull mulmod(ull a, ull b){ return (unsigned __int128)a * b % MOD; }
int n;
vector<ull> h, pw;
bool check(int L){ // có xâu con độ dài L xuất hiện >= 2 lần?
vector<ull> v;
for(int i = 0; i + L <= n; i++) v.push_back((h[i + L] + MOD - mulmod(h[i], pw[L])) % MOD);
sort(v.begin(), v.end());
return adjacent_find(v.begin(), v.end()) != v.end(); // có hai hash bằng nhau
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
n = s.size();
h.assign(n + 1, 0); pw.assign(n + 1, 1);
for(int i = 0; i < n; i++){
h[i + 1] = (mulmod(h[i], BASE) + s[i]) % MOD;
pw[i + 1] = mulmod(pw[i], BASE);
}
int lo = 0, hi = n - 1; // check(0) luôn đúng
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(check(mid)) lo = mid; else hi = mid - 1;
}
cout << lo;
return 0;
}import sys
MOD, BASE = (1 << 61) - 1, 131
s = sys.stdin.buffer.readline().strip()
n = len(s)
h = [0] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * BASE + s[i]) % MOD
def check(L): # có xâu con độ dài L xuất hiện >= 2 lần?
pL = pow(BASE, L, MOD)
cnt = n - L + 1
return len({(x - y * pL) % MOD for x, y in zip(h[L:], h)}) < cnt # cặp (h[i + L], h[i])
lo, hi = 0, n - 1 # check(0) luôn đúng
while lo < hi:
mid = (lo + hi + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
print(lo)
- 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