Thuật toán Hash (So khớp chuỗi)

1. Đặt vấn đề

Cho một bài toán đơn giản sau:

Cho một xâu (S) và một xâu (T) chỉ gồm các ký tự Đồ thường tiếng anh từ (a) đến (z).
Kiểm tra xem xâu (T) xuất hiện trong xâu (S) tại những vị trí nào?
Input

aaaaa 
aa

Output

1 2 3 4

Thuật toán Brute-force

Để giải quyết bài toán này, ta sẽ thử kiểm tra mọi vị trí bắt đầu trên xâu (S) mà xâu (T) có thể xuất hiện với độ phức tạp (O( |S| * |T| ))
Mã giả của thuật toán trên như sau:

for i = 0 to S.size() - T.size()-1 
	if(S.substr(i, T.size()) == T)
		print(i)

Thuật toán này rất đơn giản nhưng chúng ta sẽ bị mất rất nhiều chi phí khi kiểm tra xem hai xâu có bằng nhau hay không tại mỗi vị trí (i) của xâu (S).
Chi phí kiểm tra hai xâu bằng nhau là (O(|T|)) do phải kiểm tra xem từng ký tự trong xâu đó có bằng nhau hay không.

2. Thuật toán Hash

Ý tưởng

Ý tưởng của thuật toán Hash là thay vì so sánh từng ký tự của hai xâu để biết chúng có bằng nhau hay không. Ta sẽ biểu diễn hai xâu đó dưới dạng số nguyên ở hệ cơ số 10 để việc so sánh chỉ trong một phép tính.
Vì hai xâu (S) và (T) được cấu tạo bởi 26 chữ cái tiếng anh từ (a) đến (z) nên ta có thể coi đây là một số ở hệ cơ số (26). Vậy muốn đổi xâu (T) hay xâu con của (S) thành số nguyên, ta thực hiện phép chuyển đổi từ hệ cơ số (26) thành số ở hệ cơ số (10). Rồi so sánh hai số ở hệ cơ số (10).
Để dễ biểu diễn, ta có thể coi các chữ cái từ (a) đến (z) thành các số từ (1) đến (26)
Công thức đổi số từ hệ cơ số (26) sang hệ cơ số (10)

Bước 1: Đánh số các ký tự của xâu cần đổi từ vị trí cuối đến vị trí đầu, đánh số từ (0).
Bước 2: Kết quả sau khi đổi được tính theo công thức:

Với (|S|) là độ dài của xâu (S), (num_i) là số được đánh ở vị trí thứ (i)

Ứng dụng vào bài toán so khớp chuỗi

Để đổi xâu (T) thành số ở hệ cơ số (10) thì rất đơn giản, ta chỉ việc áp dụng công thức trên là ra.
Giờ vấn đề ta cần quan tâm là làm thế nào để với mỗi vị trí (i) trong xâu (S), ta có thể đổi được xâu con (S(i…i+|T|-1)) thành số ở hệ cơ số (10) nhanh nhất rồi so sánh nó với số (T) vừa đổi là xong.

Giải pháp: Chuẩn bị mảng (H[i]) là mã hash của (S(1..i)).

Công thức tính (H):

(H_i =H_{i-1}*26+S_i)

Lấy mã hash (S(L..R)) theo công thức sau:

(Hash = H_R-H_{L-1}*26^{R-L+1})

Giải thích:

Lưu ý

Tuy nhiên, 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, ý tưởng của thuật toán Hash là thay vì so sánh hai số (a) và (b) là số ở hệ cơ số (10) mà hai xâu biểu diễn, ta sẽ so sánh (a text{ mod } MOD) và (b text{ mod } MOD). Nghĩa là:

(a text{ mod } MOD = b text{ mod } MOD <=> a = b)

Dễ thấy, cách so sánh bên trên là sai lầm nhưng để giảm thời gian chạy ta phải chấp nhận giảm độ chính xác. Để giảm xác suất xảy ra sai, và cụ thể là (1/MOD) cho một truy vấn, các bạn cần chọn hệ cơ số và modulo thỏa mãn đồng thời:

• hệ cơ số ((base)) là số nguyên tố lớn hơn số lượng các chữ cái của xâu (S).
• (MOD) là số nguyên tố lớn nhất có thể.
• Chỉ so sánh hai xâu có cùng độ dài.

Cách đánh số cho các ký tự

Các ký tự sẽ được đánh số bắt đầu từ 1 để tránh những xâu như “001”, “01”, “1” có giá trị bằng nhau.
Ví dụ xâu chỉ chứa các ký tự (A, T, G, X). Ta có thể đánh số (A = 1, B = 2, G = 3, X = 4).

Cách chọn hệ cơ số

Thường thì ta sẽ làm việc trên xâu chỉ gồm các ký tự thuộc bảng mã ASCII gồm 256 ký tự. Có thể chọn (base) là (31, 71…)

Cách chọn Modulo

Chọn số (MOD) lớn nhất có thể, tuy nhiên ở hàm (getHash()) ta có một phép nhân hai số có giá trị (0… MOD-1). Nên ta chỉ có thể chọn số (MOD ~10^9)
Không nên chọn số (MOD) là (1000000007 (10^9+7)).

Đối với những test được sinh random, tỉ lệ xảy ra sai là rất thấp. Nhưng nếu bạn làm bài trên Codeforces, người khác có thể đọc code của bạn và sinh ra test để bắt những trường hợp sai. Số (MOD= 1000000007) là số được sử dụng phổ biến nên rất dễ bị hack.

Có thể chọn nhiều số (MOD) cùng lúc và kiểm tra.

Hash tràn số

Khi dùng nhiều phép mod sẽ khiến chương trình chạy chậm. Để tăng tốc độ người ta sử dụng kỹ thuật Hash tràn số, nghĩa là khi sử dụng kiểu dữ liệu 64-bit, khi tính toán một số vượt quá phạm vi cho phép, số đó sẽ tự động được gán cho kết quả sau khi mod cho (2^{64})
Ta thấy số (MOD=2^{64}) không phải là một số nguyên tố khiến cho hàm Hash sẽ dễ sai. Cách làm này sẽ hoàn toàn ổn nếu test được sinh random. Tuy nhiên, giám khảo vẫn có thể cho một vài trường hợp khiến cho code không AC được. Vậy nên hãy cân nhắc trước khi sử dụng nhé.

Đánh giá độ phức tạp của thuật toán Hash

• Chi phí chuẩn bị mảng (H) là (O(|S|)).
• Chi phí so khớp chuỗi cho từng vị trí (O(1))

3. Code thuật toán Hash

Ở code này sử dụng 2 số (MOD), bạn có thể sử dụng (1 – 4) số (MOD) khác nhau tuỳ theo mong muốn nhé.

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000005
#define base 31
#define MOD1 111539786
#define MOD2 1000000007

long long h1[MAXN], mu1[MAXN], h2[MAXN], mu2[MAXN];
string s, t;
vector<int> kq;
long long getHash1(int l, int r){
	return (h1[r] - h1[l-1]*mu1[r-l+1]%MOD1 + MOD1)%MOD1;
}
long long getHash2(int l, int r){
	return (h2[r] - h2[l-1]*mu2[r-l+1]%MOD2 + MOD2)%MOD2;
}
int main() {
	cin>>s>>t;
	//Thêm ký tự # vào đầu để các ký tự được đánh số từ 1.
	s="#"+s;
	//Chuẩn bị mảng H
	mu1[0]=1; mu2[0]=1;
	for(int i = 1; i < s.size(); i++){
		h1[i] = (h1[i-1]*base + (s[i]-'a'+1)) % MOD1;
		mu1[i]= (mu1[i-1]*base) % MOD1;
		h2[i] = (h2[i-1]*base + (s[i]-'a'+1)) % MOD2;
		mu2[i]= (mu2[i-1]*base) % MOD2;
	}
	//Tính mã Hash của T
	long long hashT1 = 0, hashT2 = 0;
	for(int i = 0; i < t.size(); i++){
		hashT1 = (hashT1*base + (t[i]-'a'+1)) % MOD1;
		hashT2 = (hashT2*base + (t[i]-'a'+1)) % MOD2;
	}
	//So khớp
	
	for(int i = 1; i < s.size() - t.size() + 1; i++){
		long long h1 = getHash1(i, i+t.size()-1);
		long long h2 = getHash2(i, i+t.size()-1);
		if(hashT1 == h1 && hashT2 == h2)
			kq.push_back(i);
	}
//	cout<<kq.size()<<endl;
	for(int i = 0; i<kq.size(); i++)
		cout<<kq[i]<<" ";
	return 0;
}

4. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn