Chuỗi Con Xuất Hiện K Lần (DTKSUB)
Đề bài
DTKSUB – Chuỗi con xuất hiện K lần
Sau những kỳ công trong những cuộc chinh phục các cấu trúc dữ liệu đặc biệt, tình bạn giữa pirate và duyhung123abc ngày càng trở nên khăng khít. Rồi bỗng một ngày nọ, duyhung123abc bỗng ra đi không một lời từ biệt, chỉ để lại một mẩu giấy cho pirate. Mẩu giấy viết rằng: "Em ơi, anh còn nặng nợ toán lý hóa anh, chưa thể một lòng theo đuổi tin học. Em hãy làm nốt công việc mà anh em ta còn dang dở!". pirate đọc xong, nước mắt giàn giụa. Nếu khi hai người gặp nhau, vui sướng như khi Engels gặp Marx, thì trong giây phút chia ly này, lòng pirate đau đớn như khi Đỗ Phủ tiễn người tri kỉ Lý Bạch lên đường.
Mất đi người anh cả, pirate như con thuyền mất phương hướng. Cuối cùng, sau những đêm không ngủ, anh quyết định rằng mình sẽ đợi cho đến khi duyhung123abc trả xong nợ công danh và quay trở về sẽ tiếp tục nghiên cứu các cấu trúc dữ liệu đặc biệt. Còn bây giờ, anh ta sẽ đi một con đường mới, đi vào một thế giới mới, thế giới của các THUẬT TOÁN VỀ CHUỖI. Tuy cô độc một mình, nhưng với niềm tin của mình, pirate đã lên đường ngay mà không có chút do dự.
Nhưng trớ trêu thay, vạn sự khởi đầu nan. Thử thách đầu tiên mà con người trẻ tuổi này gặp phải thật đau đầu. Anh ta được cho trước một chuỗi $S$ có độ dài $N$ và một số $K$. Thử thách được hoàn thành chỉ khi anh ấy đưa ra được độ dài của chuỗi dài nhất xuất hiện ít nhất $K$ lần trong chuỗi $S$. Làm sao đây! Vừa vực dậy sau một cú sốc lớn, pirate rất cần sự giúp đỡ của các bạn để không mất đi sự nhiệt huyết của mình!
Dữ liệu vào: gồm 2 dòng:
- Dòng 1: hai số nguyên $N$ và $K$ $(1 \le N \le 50000;\ 1 \le K \le 200)$.
- Dòng 2: chuỗi $S$ có độ dài $N$ (gồm các chữ cái in thường viết liên tiếp nhau).
Kết quả: gồm một dòng duy nhất là độ dài của chuỗi dài nhất xuất hiện ít nhất $K$ lần trong chuỗi $S$.
Lưu ý: một chuỗi $A[1 \ldots m]$ được gọi là xuất hiện trong chuỗi $B[1 \ldots n]$ $K$ lần khi và chỉ khi tồn tại $K$ vị trí $i$ phân biệt sao cho $A[1 \ldots m] = B[i \ldots i+m-1]$.
Giới hạn: thời gian 0.38 giây, bộ nhớ 512 MB. Đọc dữ liệu từ bàn phím, in ra màn hình.
5 2
xxxxx4Lời mở đầu
Đây là một bài xử lý xâu rất hay để các bạn làm quen với thuật toán Hash (băm xâu) – một kỹ thuật cực kỳ hay dùng trong các kỳ thi. Bài này cũng là ví dụ đẹp cho kỹ thuật chặt nhị phân trên tập kết quả. Mình sẽ đi từ cách vét cạn đơn giản nhất, rồi cải tiến từng bước một cho tới khi AC, để các bạn thấy rõ vì sao lại phải nghĩ tới hash. Hy vọng mang đến được giá trị cho các bạn 😇.
Trước tiên mình tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu: bạn được cho một xâu $s$ có độ dài $n$ và một số $k$. Hãy tìm độ dài của xâu con dài nhất (các ký tự liên tiếp nhau) xuất hiện ít nhất $k$ lần trong xâu $s$. Các lần xuất hiện được phép chồng lên nhau, chỉ cần vị trí bắt đầu khác nhau là được.
Giải thích ví dụ: $n = 5$, $k = 2$, $s = $ xxxxx. Xâu con xxxx có độ dài $4$ xuất hiện 2 lần: từ vị trí $[1 \ldots 4]$ và từ vị trí $[2 \ldots 5]$ (hai lần này chồng lên nhau, vẫn tính nha). Còn xâu dài $5$ chỉ có đúng 1 xâu là cả xâu $s$, xuất hiện 1 lần, không đủ $k = 2$. Vậy đáp án là $4$.
Thêm một ví dụ của mình: $n = 16$, $k = 2$, $s = $ abcdefghabcdeegh. Đáp án là $5$, chính là xâu abcde (xuất hiện ở vị trí bắt đầu $1$ và $9$). Không có xâu con nào dài $6$ xuất hiện từ 2 lần trở lên.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi xâu con + map
Cách làm đơn giản nhất của bài này chính là vét cạn, tức ta sẽ sinh ra mọi xâu con có thể. Đầu tiên ta cần trả lời câu hỏi: xâu con dài nhất có thể xuất hiện ít nhất $k$ lần sẽ có độ dài tối đa là bao nhiêu?
Một xâu con độ dài $i$ thì có $n - i + 1$ vị trí bắt đầu. Muốn xuất hiện ít nhất $k$ lần thì phải có ít nhất $k$ vị trí bắt đầu, tức $n - i + 1 \ge k$, hay $i \le n - k + 1$. Nhìn lại ví dụ: $n - k + 1 = 5 - 2 + 1 = 4$, lúc đó ta có đúng $k = 2$ xâu con độ dài $4$, và nếu $k$ xâu con đó đều bằng nhau (như xxxx) thì ta có ngay xâu con dài nhất xuất hiện $k$ lần.
Từ đó ta sẽ sinh ra mọi xâu con có độ dài $i$ $(1 \le i \le n - k + 1)$ rồi kiểm tra xem có xâu con nào độ dài $i$ xuất hiện $\ge k$ lần không. Để làm điều đó, ta có thể cho hết các xâu con độ dài $i$ vào một vector, sắp xếp tăng dần rồi duyệt xem có xâu nào lặp lại $\ge k$ lần. Hoặc đơn giản hơn là dùng cấu trúc dữ liệu map<key, value>:
- key là các xâu con (
string), value là số lần xuất hiện của xâu con đó (int). - Khi một xâu con độ dài $i$ nào đó được đếm tới đúng bằng $k$ thì chứng tỏ tồn tại xâu con độ dài $i$ xuất hiện ít nhất $k$ lần.
Một điều nữa: ta đang cần tìm xâu con dài nhất, nên ta tạo các xâu con có độ dài từ $n - k + 1$ chạy ngược về $1$. Lúc này độ dài $i$ đầu tiên thoả mãn chính là kết quả của bài toán luôn (vì ta thử từ xâu dài nhất có thể rồi giảm dần từng chút một), in ra rồi kết thúc chương trình.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
string s;
cin >> n >> k >> s;
for(int i = (n - k + 1); i >= 1; --i) {
map<string, int> mp;
for(int j = 0; j <= n - i; ++j) {
string tmp = s.substr(j, i);
mp[tmp]++;
if(mp[tmp] == k) {
cout << i;
return 0;
}
}
}
cout << 0;
return 0;
}import sys
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
s = data[2]
def solve():
for i in range(n - k + 1, 0, -1):
mp = {}
for j in range(0, n - i + 1):
tmp = s[j:j + i]
mp[tmp] = mp.get(tmp, 0) + 1
if mp[tmp] == k:
return i
return 0
print(solve())Các bạn bấm Tiếp để chạy tay từng dòng. Xâu con đang xét được tô vàng trên xâu $s$, còn bảng mp hiện số lần xuất hiện của từng xâu con (với map thì các key luôn được sắp xếp theo thứ tự từ điển):
Giải thích 1 số chỗ trong code ở trên:
for(int j = 0; j <= n - i; ++j): với xâu con độ dài $i$ và vị trí đầu tiên của xâu $s$ là $0$, thì xâu con đó chỉ được xuất phát từ $0$ tới $n - i$ mà thôi ($0 \le j \le n - i$). Vì nếu xuất phát từ vị trí $n - i$ thì ký tự cuối cùng của xâu con đã là ký tự $n - 1$ (ký tự cuối cùng của $s$) rồi.string tmp = s.substr(j, i);: hàmsubstr(j, i)tạo ra xâu con bắt đầu từ vị trí $j$ và có độ dài $i$ trong xâu $s$, rồi gán vàotmp.cout << 0;: đã thử mọi độ dài từ $n - k + 1$ về $1$ mà vẫn không tìm được xâu con nào xuất hiện ít nhất $k$ lần (nếu có thì đã in ra và thoát chương trình rồi), nên kết quả là $0$. Trường hợp này xảy ra khi $k \gt n$ (lúc đó $n - k + 1 \le 0$, vòng lặp không chạy lần nào).
Đánh giá độ phức tạp của cách làm này:
- Thời gian: có tới $n - k + 1$ độ dài phải thử, mỗi độ dài sinh ra cỡ $n$ xâu con, mỗi xâu con mất $O(i)$ để
substrvà so sánh trongmap(cộng thêm $\log n$ lần so sánh). Tệ nhất cỡ $O(n^3 \log n)$. - Không gian:
maplưu tới $n$ xâu con, mỗi xâu dài tới $n$ ký tự: $O(n^2)$.
Một gợi ý nhỏ để tối ưu thêm là thay chỗ khai báo map<string, int> mp; thành unordered_map<string, int> mp;. Tức là lưu theo hash table (bảng băm) thay vì lưu theo tree (cây), thì chi phí tìm kiếm (truy xuất) chỉ còn $O(1)$ thay vì $O(\log n)$. Sửa như vậy ta vẫn chỉ ăn được 6 test, nhưng nhìn vào thời gian chạy của các test AC thì sẽ thấy code chạy nhanh hơn trước.
Mình cũng cảnh báo là về mặt lý thuyết, unordered_map trong trường hợp xấu nhất khi tìm một phần tử có thể lên đến $O(n)$ – đó là khi hàm băm không tốt dẫn đến xung đột. Điều này các bạn không quản lý được mà do cơ chế của cấu trúc dữ liệu có sẵn, xem như là phó mặc cho nó. Trong khi đó map lưu theo cây nên mọi trường hợp đều đảm bảo $O(\log n)$, tuy độ phức tạp cao hơn nhưng dùng map ta cảm thấy yên tâm hơn 🤣. Vậy nên không phải lúc nào unordered_map cũng tốt hơn map. Kinh nghiệm của mình: code dùng map mà bị TLE thì cứ thử thay bằng unordered_map rồi nộp lại, được thêm test thì tốt, còn thấy test đang AC chuyển sang TLE thì quay xe lại map thôi 🤪. Ở bài này code chạy nhanh hơn nên từ cách sau mình chuyển qua dùng unordered_map nha.
Cách 2Chặt nhị phân trên tập kết quả + unordered_map<string, int>
Đến với cách làm cải tiến hơn, các bạn cần nhận ra điều này:
- Khi có xâu con độ dài $i$ xuất hiện ít nhất $k$ lần trong $s$, thì chắc chắn cũng có xâu con độ dài $\lt i$ xuất hiện ít nhất $k$ lần (còn độ dài $\gt i$ thì ta chưa biết).
- Ngược lại, khi không có xâu con độ dài $i$ nào xuất hiện ít nhất $k$ lần, thì chắc chắn các độ dài $\gt i$ cũng không có (còn độ dài $\lt i$ thì ta chưa biết).
Hoặc phát biểu cách khác: giả sử độ dài của xâu con dài nhất xuất hiện ít nhất $k$ lần là $ans$. Thì với mọi độ dài $x \le ans$ luôn tồn tại xâu độ dài $x$ xuất hiện ít nhất $k$ lần, còn với mọi độ dài $x \gt ans$ thì không tồn tại.
Mình lấy ví dụ cho các bạn dễ hình dung: $n = 16$, $k = 2$, $s = $ abcdefghabcdeegh, kết quả là $5$ (xâu abcde).
- Xâu
abcde(độ dài $5$) xuất hiện 2 lần, thì chắc chắn xâuabcd(độ dài $4$) cũng xuất hiện ít nhất 2 lần – vì mỗi lầnabcdexuất hiện thì bên trong có sẵn một lầnabcdrồi. Tương tự vớiabc,ab,a. Vậy độ dài $i$ thoả thì các độ dài bé hơn cũng thoả. - Với độ dài $6$, ta không tìm ra xâu con nào xuất hiện ít nhất 2 lần. Vậy chắc chắn cũng không có xâu con độ dài $\ge 6$ nào thoả. Vì nếu có, theo điều vừa thấy ở trên thì xâu con độ dài $6$ (lấy phần đầu của nó) cũng phải thoả – vô lý.
| Độ dài | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | 15 |
|---|---|---|---|---|---|---|---|---|---|
| Có xâu xuất hiện ≥ 2 lần? | Có | Có | Có | Có | Có | Không | Không | … | Không |
Kết quả có dạng "Có Có … Có Không Không … Không" – một dãy đơn điệu. Nhận ra được điều này thì ta áp dụng được tìm kiếm nhị phân trên tập kết quả (mình hay gọi là chặt nhị phân trên tập kết quả). Tập kết quả chính là 2 đầu mút của vòng for(i) ở cách 1: kết quả nằm trong khoảng từ $1$ tới $n - k + 1$ (nếu không thì là $0$ – ta khởi tạo biến kết quả bằng $0$ nên tập kết quả chỉ cần từ $1$ tới $n - k + 1$).
Việc kiểm tra xâu con độ dài $m$ có xuất hiện ít nhất $k$ lần hay không thì vẫn làm giống phần vét cạn thôi, nhưng giờ ta chuyển vào một hàm check(m) để tiện gọi.
Minh hoạ: chặt nhị phân trên độ dài
Các bạn nhập xâu $s$ và $k$ rồi bấm Tiếp. Hàng ô phía trên là các độ dài từ $1$ tới $n - k + 1$: ô vàng là $m$ đang kiểm tra, xanh là độ dài đã kiểm tra "Có", đỏ là "Không", mờ là đoạn đã bị loại. Bước cuối mình tô hết các độ dài để các bạn thấy dãy "Có… Không…" đơn điệu như thế nào:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int n, k;
string s;
bool check(int m) {
unordered_map<string, int> ump;
for(int i = 0; i <= n - m; ++i) {
string tmp = s.substr(i, m);
ump[tmp]++;
if(ump[tmp] == k) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
cin >> s;
int res = 0, l = 1, r = n - k + 1;
while(l <= r) {
int m = (l + r) / 2;
if(check(m)) {
res = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << res;
return 0;
}import sys
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
s = data[2]
def check(m):
ump = {}
for i in range(0, n - m + 1):
tmp = s[i:i + m]
ump[tmp] = ump.get(tmp, 0) + 1
if ump[tmp] == k:
return True
return False
res, l, r = 0, 1, n - k + 1
while l <= r:
m = (l + r) // 2
if check(m):
res = m
l = m + 1
else:
r = m - 1
print(res)Đánh giá độ phức tạp của cách làm này:
- Thời gian: vòng
while(l <= r)chỉ chạy $O(\log n)$ lần. Nhưng hàmcheck(m)tốn $O(n \cdot m)$: vòngfor(i)chạy qua gần như toàn bộ xâu $s$, và mỗi lầnsubstrphải copy xâu độ dài $m$ (đó là ta coi thao tác trênunordered_maplà $O(1)$, chứ thực ra băm một xâu độ dài $m$ cũng tốn $O(m)$). Lần check đầu tiên $m \approx n / 2$ nên tốn cỡ $n^2 / 2$; thay $n = 5 \cdot 10^4$ vào là $1.25 \cdot 10^9$ phép tính – chắc chắn TLE. - Không gian:
unordered_map<string, int>lưu tới cỡ $n / 2$ xâu, mỗi xâu dài $n / 2$ ký tự: $O(n^2)$ – ăn rất nhiều bộ nhớ.
map thì chỉ được 8 test). Lúc nộp mình thấy ở test bị TLE, code ăn tới hơn 200 MB bộ nhớ. Mình đo lại với $n = 50000$, xâu ngẫu nhiên, $k = 200$: chạy khoảng 2.7 giây và ăn tới khoảng 600 MB – vì lần check đầu tiên ($m = 25000$) phải lưu cả $25001$ xâu, mỗi xâu dài $25000$ ký tự!Cách 3Đổi xâu thành số bằng hash<string>
Để giải quyết việc ăn quá nhiều bộ nhớ, sao ta không thử chuyển từ xâu về 1 số: mỗi xâu khác nhau cho một số khác nhau, các xâu giống nhau cho số giống nhau. Lúc này key của unordered_map là một số nguyên nên ăn ít bộ nhớ hơn rất nhiều. Để làm điều đó ta dùng hash function có sẵn trong C++:
hash<string> hasher; rồi cần chuyển xâu nào thành số thì gọi hasher(xâu cần chuyển). Kiểu dữ liệu trả về là size_t (số nguyên không âm 64 bit). Bạn nào muốn tìm hiểu thêm thì đọc ở cppreference nha.Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int n, k;
string s;
bool check(int m) {
hash<string> hasher;
unordered_map<size_t, int> ump;
for(int i = 0; i <= n - m; ++i) {
size_t tmp = hasher(s.substr(i, m));
ump[tmp]++;
if(ump[tmp] == k) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
cin >> s;
int res = 0, l = 1, r = n - k + 1;
while(l <= r) {
int m = (l + r) / 2;
if(check(m)) {
res = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << res;
return 0;
}import sys
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
s = data[2]
def check(m):
ump = {}
for i in range(0, n - m + 1):
tmp = hash(s[i:i + m]) # đổi xâu con thành 1 số nguyên (giống hasher trong C++)
ump[tmp] = ump.get(tmp, 0) + 1
if ump[tmp] == k:
return True
return False
res, l, r = 0, 1, n - k + 1
while l <= r:
m = (l + r) // 2
if check(m):
res = m
l = m + 1
else:
r = m - 1
print(res)Bản Python mình dùng hàm hash() có sẵn của Python, ý tưởng y hệt. Trong khung chạy tay dưới đây, giá trị hasher(...) được tính đúng như thư viện GCC (libstdc++) tính, nên các con số khớp với khi các bạn chạy thật bằng g++ 64 bit nha:
Đánh giá độ phức tạp của cách làm này: code ăn ít bộ nhớ hơn rất nhiều (mình đo cùng test ở trên chỉ còn khoảng 11 MB thay vì 600 MB) và ăn được 10 test đầu. Tuy nhiên hàm check() vẫn chạy lâu: substr vẫn tốn $O(m)$, và hasher(xâu) cũng phải đọc hết xâu truyền vào nên tốn thêm $O(m)$ nữa. Độ phức tạp thời gian vẫn như cách 2 (mình đo khoảng 0.9 giây với $n = 50000$, trong khi giới hạn chỉ 0.38 giây) nên vẫn TLE thôi.
Cách 4Thuật toán Hash xâu – O(n log n)
Để AC bài này ta sẽ dùng thuật toán Hash. Bạn nào chưa biết thì mình tiến cử bài viết rất chi tiết của VNOI: wiki.vnoi.info/algo/string/hash. Ở đây mình sẽ không đi quá sâu vào lý thuyết, mà tập trung vào cách áp dụng: dùng hash trong hàm check(m) để lấy "mã số" của các xâu con độ dài $m$ trong $O(1)$ thay vì $O(m)$, đồng thời key là số nên ăn ít bộ nhớ.
Bước 1: Xâu cũng là một con số trong hệ cơ số nào đó
Đầu tiên ta cần nắm rõ về hệ cơ số (hệ đếm). Thân thuộc nhất là hệ thập phân (cơ số 10): số $123$ chính là $1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0$.
- Hệ nhị phân (cơ số 2) dùng 2 chữ số $0, 1$: $123$ viết là $1111011$, vì $1 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 123$. Các số khác nhau ở hệ 2 thì đổi ra hệ 10 cũng khác nhau (ví dụ $10_2 = 2$, $11_2 = 3$), các số giống nhau thì giá trị giống nhau.
- Hệ thập lục phân (cơ số 16) dùng 16 ký tự $0 \ldots 9, A \ldots F$ (A = 10, B = 11, …, F = 15): $123$ viết là $7B$, vì $7 \cdot 16^1 + 11 \cdot 16^0 = 123$. Tương tự, $FE_{16} = 254$ và $EF_{16} = 239$ là khác nhau.
Giờ ta làm tương tự với xâu: gán a = 1, b = 2, …, z = 26 – tổng cộng 26 chữ cái tương đương 26 "chữ số". Vậy một xâu có thể xem là một số ở hệ cơ số 26 (hoặc bất kỳ cơ số nào $\ge 26$). Ví dụ xâu abc là dãy chữ số $(1, 2, 3)$:
- Ở hệ cơ số 26: $1 \cdot 26^2 + 2 \cdot 26^1 + 3 \cdot 26^0 = 731$.
- Ở hệ cơ số 31 (vẫn chỉ dùng các chữ số từ 1 tới 26): $1 \cdot 31^2 + 2 \cdot 31^1 + 3 \cdot 31^0 = 1026$.
ab đổi ra hệ 26 là $01$, giá trị $0 \cdot 26 + 1 = 1$; còn xâu b là $1$, giá trị cũng bằng $1$. Với con số thì $01 = 1$, nhưng với xâu thì ab đâu có bằng b! Gán a = 1 (không có chữ số 0) là giải quyết được trường hợp này.Bước 2: Chia dư để con số không quá lớn
Vấn đề tiếp theo: giá trị của xâu sẽ rất lớn, xâu có 3 ký tự mà đã ra $1026$ rồi, xâu dài vài chục ký tự là vượt phạm vi lưu trữ số nguyên của máy tính luôn. Để khắc phục, ta chia lấy dư giá trị đó cho một số nguyên tố đủ lớn, kết quả gọi là mã hash của xâu.
Dễ thấy có thể có những xâu khác nhau mà chia dư ra giống nhau, nên 2 xâu có mã hash bằng nhau thì chưa chắc đã giống nhau (gọi là đụng độ – collision). Ta chấp nhận điều này trong thuật toán hash, vì với số nguyên tố cỡ $10^9$ thì xác suất hai xâu khác nhau cho trước có cùng mã hash chỉ khoảng $\frac{1}{10^9}$ – vô cùng nhỏ. Để xác suất sai nhỏ nhất có thể, ta chọn:
- $base$ là số nguyên tố và $\ge 26$. Bài xử lý xâu chỉ có chữ cái thường chọn $base = 31$.
- Số dùng để chia dư, gọi là $mod$, cũng là số nguyên tố và đủ lớn. Bài này chọn $mod = 10^9 + 7$.
Bước 3: Mã hash của mọi tiền tố – mảng hashS
Gọi $hashS[i]$ là mã hash của xâu con từ vị trí $1$ tới $i$. Lấy ví dụ $s = $ abcd:
| i | Xâu 1…i | Mã hash | Tính từ hashS[i - 1] |
|---|---|---|---|
| 1 | a | $1 \cdot 31^0 = 1$ | $hashS[0] \cdot 31 + 1 = 0 \cdot 31 + 1 = 1$ |
| 2 | ab | $1 \cdot 31^1 + 2 \cdot 31^0 = 33$ | $1 \cdot 31 + 2 = 33$ |
| 3 | abc | $1 \cdot 31^2 + 2 \cdot 31 + 3 = 1026$ | $33 \cdot 31 + 3 = 1026$ |
| 4 | abcd | $1 \cdot 31^3 + 2 \cdot 31^2 + 3 \cdot 31 + 4 = 31810$ | $1026 \cdot 31 + 4 = 31810$ |
Cho $hashS[0] = 0$, mỗi lần thêm một ký tự vào cuối thì "dịch" số cũ sang trái một hàng (nhân với $base$) rồi cộng chữ số mới (giống như thêm chữ số vào cuối số $12$ thành $123 = 12 \cdot 10 + 3$). Chữ số của ký tự $s[i]$ là s[i] - 'a' + 1 (phải $+1$ vì ta gán a = 1).
Trong code mình gán s = " " + s; để chữ cái đầu tiên nằm ở vị trí $1$ và chữ cái cuối cùng ở vị trí $n$.
Bước 4: Lấy mã hash của đoạn [l, r] trong O(1)
Mình lấy ví dụ với số ở hệ 10 cho dễ hình dung: số $67895$, đánh số các chữ số từ trái qua phải là $1, 2, 3, 4, 5$. Muốn lấy giá trị đoạn từ chữ số thứ $2$ tới $4$ (tức $789$) thì làm sao? Ta lấy tiền tố tới $4$ là $6789$, trừ đi tiền tố tới $1$ là $6$ nhưng đã "dịch" sang trái $3$ hàng (đoạn $[2, 4]$ có $3$ chữ số):
$6789 - 6 \cdot 10^3 = 789$
Với hệ cơ số $base$ cũng tương tự thôi:
trong đó $r - l + 1$ là số ký tự của đoạn.
Hai chú ý khi cài đặt:
- Tránh số âm: $hashS[r] - hashS[l-1] \cdot base^{r-l+1}$ có thể âm. Theo đồng dư thức, $(a - b) \bmod mod = \big((a \bmod mod) - (b \bmod mod) + mod\big) \bmod mod$. $hashS[r]$ đã chia dư từ trước rồi, ta chỉ cần chia dư phần tích, rồi cộng thêm $mod$ và chia dư tất cả cho $mod$:
(hashS[r] - (hashS[l - 1] * p[r - l + 1]) % mod + mod) % mod. - Tính sẵn luỹ thừa: dùng vòng
forđể tính $base^{r-l+1}$ mỗi lần thì rất tốn thời gian; luỹ thừa nhị phân thì mất $O(\log)$, nhanh nhưng chưa nhanh nhất. Vì $r - l + 1$ chỉ nằm trong khoảng $1 \ldots n$, ta tính sẵn mảng $p[i] = base^i \bmod mod$ với $p[0] = 1$ và $p[i] = p[i-1] \cdot base \bmod mod$ (vì $a^n = a^{n-1} \cdot a$). Từ đó lấy $base^{r-l+1}$ chỉ mất $O(1)$.
Cuối cùng, trong hàm check(m), thay vì lấy xâu con bắt đầu từ $i$ dài $m$, ta lấy mã hash của nó, chính là getHashS(i, i + m - 1) (xâu con bắt đầu từ ký tự $i$, dài $m$ thì kết thúc ở ký tự $i + m - 1$). Bên ngoài vẫn chặt nhị phân như bình thường.
Minh hoạ: tính hashS và trượt cửa sổ độ dài m
Các bạn nhập xâu $s$ và độ dài $m$ rồi bấm Tiếp. Phần đầu tính mảng $hashS$ từng ô; phần sau trượt cửa sổ độ dài $m$, mỗi vị trí lấy mã hash bằng công thức $O(1)$ ở trên và đếm vào bảng. Các bạn để ý những xâu con giống nhau luôn ra cùng một mã hash nha:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll base = 31;
const int N = 5 * 1e4 + 5;
int n, k;
string s;
ll p[N], hashS[N];
void init() {
s = " " + s;
p[0] = 1;
for(int i = 1; i <= n; ++i) {
p[i] = p[i - 1] * base % mod;
}
hashS[0] = 0;
for(int i = 1; i <= n; ++i) {
hashS[i] = (hashS[i - 1] * base + s[i] - 'a' + 1) % mod;
}
}
ll getHashS(int l, int r) {
return (hashS[r] - (hashS[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}
bool check(int m) {
unordered_map<ll, int> ump;
for(int i = 1; i + m - 1 <= n; ++i) {
ll tmp = getHashS(i, i + m - 1);
ump[tmp]++;
if(ump[tmp] == k) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
cin >> s;
init();
int res = 0, l = 1, r = n - k + 1;
while(l <= r) {
int m = (l + r) / 2;
if(check(m)) {
res = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << res;
return 0;
}import sys
MOD = 10**9 + 7
BASE = 31
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
s = " " + data[2]
p = [1] * (n + 1)
hashS = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = p[i - 1] * BASE % MOD
for i in range(1, n + 1):
hashS[i] = (hashS[i - 1] * BASE + ord(s[i]) - ord('a') + 1) % MOD
def getHashS(l, r):
return (hashS[r] - hashS[l - 1] * p[r - l + 1]) % MOD # % của Python luôn cho số không âm
def check(m):
ump = {}
for i in range(1, n - m + 2):
tmp = getHashS(i, i + m - 1)
ump[tmp] = ump.get(tmp, 0) + 1
if ump[tmp] == k:
return True
return False
res, l, r = 0, 1, n - k + 1
while l <= r:
m = (l + r) // 2
if check(m):
res = m
l = m + 1
else:
r = m - 1
print(res)Giải thích 1 số chỗ trong code ở trên:
const int N = 5 * 1e4 + 5;: đây là độ dài tối đa của xâu, mình thường cộng thêm 5 cho chắc. Dùng để khai báo mảngpvàhashScó $N$ phần tử.init();: hàm này dùng để khởi tạo mảngpvà mảnghashS.hashS[l - 1] * p[r - l + 1]: cả hai thừa số đều $\lt mod \approx 10^9$ nên tích $\lt 10^{18}$, vừa đủ tronglong long(tối đa khoảng $9.2 \cdot 10^{18}$). Đó là lý do phải khai báollchứ không dùngint.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$. Thực chất là $O(3n)$ từ mảng
p, mảnghashSvàunordered_map, mỗi cái đều tốn $O(n)$; theo quy tắc Big-O thì là $O(n)$. - Thời gian: $O(n \log n)$. Hàm
check(m)chỉ tốn $O(n)$ vìgetHashSmất $O(1)$ (và coi thao tác trênunordered_maplà $O(1)$); chặt nhị phân gọicheck$O(\log n)$ lần. Hàminit()tốn thêm $O(2n)$, nên tổng cộng là $O(n \log n)$.
Với cách trên là ta đã AC được bài này rồi. Tuy nhiên đây không phải cách nhanh nhất; cách "xịn" nhất cho bài này là dùng Suffix Array, nhưng nó khá phức tạp và không dễ cài đặt như thuật toán hash nên mình chỉ giải theo hướng hash thôi nha.
Lúc kiểm tra lời giải này, mình phát hiện một điều rất đáng lưu ý. Xác suất $\frac{1}{10^9}$ ở trên là cho một cặp xâu cụ thể. Nhưng trong một lần check(m) ta có tới cỡ $n = 5 \cdot 10^4$ mã hash, tức cỡ $\frac{n^2}{2} \approx 1.25 \cdot 10^9$ cặp có thể đụng nhau! Giống như "nghịch lý ngày sinh nhật": lớp chỉ cần 23 bạn là đã có hơn 50% khả năng có 2 bạn trùng ngày sinh. Với $mod = 10^9 + 7$, mỗi lần check kỳ vọng có khoảng $1$ cặp xâu khác nhau bị trùng mã hash.
Với $k \ge 3$ thì một cặp trùng chưa gây hại (cần tới $k$ mã giống nhau). Nhưng với $k = 2$, chỉ một cặp đụng độ là check(m) trả về true sai. Mình đã thử code ở trên với 30 xâu ngẫu nhiên $n = 50000$, $k = 2$: cả 30 lần đều ra sai (ví dụ đáp án đúng là $6$ nhưng code in ra $27099$). Code vẫn AC trên VNOJ do bộ test không có trường hợp này, nhưng gặp bộ test "khó tính" hơn là toang 😅. Cách khắc phục ở ngay phần dưới.
Cách 5Bổ sung: hash kép cho chắc ăn
Cách sửa đơn giản và phổ biến nhất là dùng hai mã hash với hai số chia dư khác nhau, ở đây là $mod_1 = 10^9 + 7$ và $mod_2 = 10^9 + 9$ (cũng là số nguyên tố). Hai xâu chỉ bị coi là giống nhau khi trùng cả hai mã, nên xác suất một cặp đụng độ giảm xuống cỡ $\frac{1}{10^{18}}$; với $1.25 \cdot 10^9$ cặp thì xác suất có đụng độ chỉ còn cỡ $10^{-9}$ – yên tâm rồi.
Để vẫn dùng được unordered_map<ll, int> như cũ, ta ghép hai mã thành một số: $key = h_1 \cdot mod_2 + h_2$. Vì $0 \le h_2 \lt mod_2$ nên mỗi cặp $(h_1, h_2)$ cho đúng một $key$ khác nhau (giống như viết số có 2 "chữ số" ở hệ cơ số $mod_2$), và $key \lt (10^9 + 7)(10^9 + 9) \approx 10^{18}$ vẫn vừa long long. Phần còn lại giữ nguyên ý tưởng của cách 4, mình chỉ nhân đôi các mảng lên:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;
const ll base = 31;
const int N = 5 * 1e4 + 5;
int n, k;
string s;
ll p1[N], p2[N], hash1[N], hash2[N];
void init() {
s = " " + s;
p1[0] = p2[0] = 1;
for(int i = 1; i <= n; ++i) {
p1[i] = p1[i - 1] * base % mod1;
p2[i] = p2[i - 1] * base % mod2;
}
hash1[0] = hash2[0] = 0;
for(int i = 1; i <= n; ++i) {
hash1[i] = (hash1[i - 1] * base + s[i] - 'a' + 1) % mod1;
hash2[i] = (hash2[i - 1] * base + s[i] - 'a' + 1) % mod2;
}
}
ll getHash(ll h[], ll p[], ll mod, int l, int r) {
return (h[r] - (h[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}
bool check(int m) {
unordered_map<ll, int> ump;
for(int i = 1; i + m - 1 <= n; ++i) {
ll tmp = getHash(hash1, p1, mod1, i, i + m - 1) * mod2
+ getHash(hash2, p2, mod2, i, i + m - 1);
ump[tmp]++;
if(ump[tmp] == k) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
cin >> s;
init();
int res = 0, l = 1, r = n - k + 1;
while(l <= r) {
int m = (l + r) / 2;
if(check(m)) {
res = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << res;
return 0;
}import sys
MOD1, MOD2 = 10**9 + 7, 10**9 + 9
BASE = 31
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
s = " " + data[2]
p1 = [1] * (n + 1); p2 = [1] * (n + 1)
hash1 = [0] * (n + 1); hash2 = [0] * (n + 1)
for i in range(1, n + 1):
p1[i] = p1[i - 1] * BASE % MOD1
p2[i] = p2[i - 1] * BASE % MOD2
for i in range(1, n + 1):
c = ord(s[i]) - ord('a') + 1
hash1[i] = (hash1[i - 1] * BASE + c) % MOD1
hash2[i] = (hash2[i - 1] * BASE + c) % MOD2
def getHash(h, p, mod, l, r):
return (h[r] - h[l - 1] * p[r - l + 1]) % mod
def check(m):
ump = {}
for i in range(1, n - m + 2):
tmp = getHash(hash1, p1, MOD1, i, i + m - 1) * MOD2 \
+ getHash(hash2, p2, MOD2, i, i + m - 1)
ump[tmp] = ump.get(tmp, 0) + 1
if ump[tmp] == k:
return True
return False
res, l, r = 0, 1, n - k + 1
while l <= r:
m = (l + r) // 2
if check(m):
res = m
l = m + 1
else:
r = m - 1
print(res)Đánh giá độ phức tạp: y hệt cách 4, chỉ tốn gấp đôi số phép tính hash (vẫn rất nhẹ so với thao tác trên unordered_map). Với cùng 30 bộ test ngẫu nhiên $n = 50000$, $k = 2$ ở trên, bản hash kép ra đúng hết; thời gian chạy bản C++ khoảng 0.2–0.4 giây trên máy của mình (máy lúc đo đang khá bận nên con số dao động), cùng cỡ với cách 4.
a/b, xâu toàn chữ a, xâu tuần hoàn; $k = 2$ và $k = 200$), mình so với một bản hash kép modulo $2^{61} - 1$: cách 2 và cách 3 cho đúng nhưng chạy khoảng 3 giây và 1 giây (cách 2 ăn tới khoảng 600 MB); cách 1 chạy quá 30 giây; cách 4 chạy khoảng 0.1–0.3 giây nhưng sai ở các test ngẫu nhiên có $k = 2$ do đụng độ hash như mình đã phân tích; cách 5 đúng hết.- 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