Một lớp những bài toán rất được quan tâm trong khoa học máy tính nói chung và lập trình thi cử nói riêng, đó là xử lý xâu chuỗi. Trong lớp bài toán này, người ta thường rất hay phải đối mặt với một bài toán: tìm kiếm xâu chuỗi.
Phát biểu bài toán
- Cho một đoạn văn bản, gồm $m$ ký tự.
- Cho một đoạn mẫu, gồm $n$ ký tự.
- Máy tính cần trả lời câu hỏi: đoạn mẫu xuất hiện bao nhiêu lần trong đoạn văn bản và chỉ ra các vị trí xuất hiện đó.
Thuật toán:
Có rất nhiều thuật toán có thể giải quyết bài toán này. Người viết xin tóm tắt 2 thuật toán phổ biến được dùng trong các kì thi lập trình:
- Brute-force: Với một cách tiếp cận trực tiếp, chúng ta có thể thu được thuật toán để giải. Tuy nhiên độ phực tạp của nó là rất lớn trong trường hợp xấu nhất. Thuật toán brute-force so khớp tất cả các vị trí xuất hiện của đoạn mẫu trong đoạn văn bản. Cụ thể độ phức tạp cho thuật toán này là $O[mn]$.
- Knuth-Morris-Pratt: Hay còn được viết tắt là KMP, được phát minh vào năm 1974, bởi Donald Knuth, Vaughan Pratt và James H. Morris. Thuật toán này sử dụng một correction-array, là một thuật toán rất hiệu quả, có độ phức tạp là $O[m + n]$.
Mục đích bài viết
Trong bài viết này, người viết chỉ tập trung vào thuật toán Hash [Tên chuẩn của thuật toán này là Rabin–Karp hoặc Rolling Hash, tuy nhiên ở Việt Nam thường được gọi là Hash]. Theo như bản thân người viết đánh giá, đây là thuật toán rất hiệu quả đặc biệt là trong thi cử. Nó hiệu quả bởi 3 yếu tố: tốc độ thực thi, linh động trong việc sử dụng [ứng dụng hiệu quả] và sự đơn giản trong cài đặt.
Đầu tiên, người viết xin được trình bày về thuật toán này. Sau đó, người viết sẽ trình bày một vài ứng dụng, cách sử dụng và phát triển thuật toán Hash trong các bài toán tin học.
Thuật toán Hash
Ký hiệu
- Tập hợp các chữ cái được sử dụng: $\Sigma$
- Đoạn con từ $i$ đến $j$ của một xâu $s$: $s[i..j]$
- Đoạn văn bản: $T[1..m]$
- Đoạn mẫu: $P[1..n]$
Chúng ta cần tìm ra tất cả các vị trí $i [1 \le i \le m − n + 1]$ thỏa mãn: $T[i..i+n−1] = P$.
Mô tả thuật toán
Để đơn giản, giả sử rằng $\Sigma = {a, b, …, z}$ [nói cách khác, $\Sigma$ chỉ gồm các chữ cái in thường]. Để biểu diễn một xâu, thay vì dùng chữ cái, chúng ta sẽ chuyển sang biểu diễn dạng số. Ví dụ: xâu aczd được viết dưới dạng số là một dãy gồm 4 số: [1,3,26,4]. Như vậy, một xâu được biểu diễn dưới dạng một số ở hệ cơ số $base$ với $base > 26$. Từ đây suy ra, 2 xâu bằng nhau khi và chỉ khi biểu diễn của 2 xâu ở hệ cơ số 10 giống nhau.
Lưu ý:
- Ở đây mình đổi chữ
athành số 1 chứ không phải số 0. Đây là chi tiết vô cùng quan trọng, để tránh 2 xâu:abcvàbcbằng nhau khi đổi ra số. Bạn có thể đọc thêm chi tiết ở phần . - Thông thường ta chọn $base$ là một số nguyên tố. Mình sẽ giải thích thêm trong phần .
Đây chính là tư tưởng của thuật toán: đổi 2 xâu từ hệ cơ số $base$ ra hệ cơ số 10, rồi đem so sánh ở hệ cơ số 10. Tuy nhiên, chúng ta nhận thấy rằng, khi đổi 1 xâu ra biểu diễn ở hệ cơ số 10, biểu diễn này có thể rất lớn và nằm ngoài phạm vi lưu trữ số nguyên của máy tính.
Để khắc phục điều này, chúng ta chuyển sang so sánh 2 biểu diễn của 2 xâu ở hệ cơ số 10 sau khi lấy phần dư cho một số nguyên đủ lớn. Cụ thể hơn: nếu biểu diễn trong hệ thập phân của xâu $a$ là $x$ và biểu diễn trong hệ thập phân của xâu $b$ là $y$, chúng ta sẽ coi $a$ bằng $b$ ‘khi và chỉ khi’ $x \bmod MOD = y \bmod MOD$ trong đó $MOD$ là một số nguyên đủ lớn.
Lưu ý: Lý do chọn $MOD$ là số nguyên tố được giải thích thêm trong phần .
Dễ dàng nhận thấy việc so sánh $x \bmod MOD$ với $y \bmod MOD$ rồi kết luận $a$ có bằng với $b$ hay không là sai. $x \bmod MOD = y \bmod MOD$ chỉ là điều kiện cần để $a$ bằng $b$ chứ chưa phải điều kiện đủ. Tuy nhiên, chúng ta sẽ chấp nhận lập luận sai này trong thuật toán Hash. Và coi điều kiện cần như điều kiện đủ. Trên thực tế, lập luận sai này có thể dẫn đến kết quả sai nếu bạn không hiểu rõ mình đang làm gì. Để hiểu rõ về tỉ lệ sai của thuật toán Hash, các bạn đọc thêm phần . Phần cũng nói thêm về cách tránh bị sai số khi cài đặt Hash.
Để đơn giản trong việc trình bày tiếp thuật toán, chúng ta sẽ gọi biểu diễn của một xâu trong hệ thập phân sau khi lấy phần dư cho $MOD$ là mã Hash của xâu đó. Nhắc lại, 2 xâu bằng nhau ‘khi và chỉ khi’ mã Hash của 2 xâu bằng nhau.
Trở lại bài toán ban đầu, chúng ta cần chỉ ra $P$ xuất hiện ở những vị trí nào trong $T$. Để làm được việc này, chúng ta chỉ cần duyệt qua mọi vị trí xuất phát có thể của $P$ trong $T$. Giả sử vị trí đó là $i$, chúng ta sẽ kiểm tra $T[i..i+n−1]$ có bằng với $P$ hay không. Để kiểm tra điều này, chúng ta cần tính được mã Hash của đoạn $T[i..i+n−1]$ và mã Hash của xâu $P$.
Để tính mã Hash của xâu $P$ chúng ta chỉ cần làm đơn giản như sau:
const base = 31;
hashP = 0
for [i : 1 .. n]
hashP = [hashP * base + P[i] - 'a' + 1] mod MODPhần khó hơn của thuật toán Hash là: Tính mã Hash của một đoạn con $T[i..j]$ của xâu $T$ $[1 \le i \le j \le N]$.
- Để hình dung cho đơn giản, xét ví dụ sau: Xét xâu $s$ và biểu diễn của nó dưới cơ số $base$: $[4,1,2,5,1,7,8]$. Chúng ta cần lấy mã Hash của đoạn con từ phần tử thứ 3 đến phần tử thứ 6, nghĩa là cần lấy mã Hash của xâu $[2,5,1,7]$. Nhận thấy, để lấy được xâu $s[3..6]$, chỉ cần lấy số $s[1..6]$ là $[4,1,2,5,1,7]$ trừ cho số [$s[1..2]$ nhân với $base^4$] là $[4,1,0,0,0,0]$ ta sẽ thu được $[2,5,1,7]$.
- Để cài đặt ý tưởng này, chúng ta cần khởi tạo $base^x \bmod MOD$ với $[0 \le x \le m]$ và mã Hash của tất cả những tiền tố của $s$, cụ thể là mã Hash của những xâu $s[1..i]$ với $[1 \le i \le m]$.
pow[0] = 1
for [i : 1 .. m]
pow[i] = [pow[i-1] * base] mod MOD
hashT[0] = 0
for [i : 1 .. m]
hashT[i] = [hashT[i-1] * base + T[i] - 'a'] mod MOD
Trong đoạn code trên, chúng ta thu được mảng $pow[i]$ [lưu lại $base^i \bmod MOD$] và mảng $hashT[i]$ [lưu lại mã Hash của $T[1..i]$].
- Để lấy mã Hash của $T[i..j]$ ta viết hàm sau:
function getHashT[i, j]:
// Chú ý rằng `- hashT[i - 1] * pow[j - i + 1]` có thể âm.
// Với 1 số ngôn ngữ như C++, toán tử mod sẽ trả kết quả sai với số âm.
// Do đó ta cần thêm "+ MOD * MOD" để đảm bảo kết quả luôn chính xác.
return [hashT[j] - hashT[i - 1] * pow[j - i + 1] + MOD * MOD] mod MODBài toán chính đã được giải quyết, và đây là chương trình chính:
for [i : 1 .. m - n +1]
if hashP = getHashT[i, i + n - 1]:
print["Match position: ", i]Mã chương trình
Chương trình sau, tôi viết bằng ngôn ngữ C++, là lời giải cho bài SUBSTR:
typedef long long ll;
const int base = 31;
const ll MOD = 1000000003;
const ll maxn = 1000111;
using namespace std;
ll POW[maxn], hashT[maxn];
ll getHashT[int i,int j] {
return [hashT[j] - hashT[i - 1] * POW[j - i + 1] + MOD * MOD] % MOD;
}
int main[] {
// Input
string T, P;
cin >> T >> P;
// Initialize
int lenT = T.size[], lenP = P.size[];
T = " " + T;
P = " " + P;
POW[0] = 1;
// Precalculate base^i
for [int i = 1; i