CTDL & giải thuật

Băm xâu: so sánh xâu con bằng Rolling Hash

So sánh từng ký tự của hai xâu con có thể tốn thời gian khi số truy vấn lớn. Rolling Hash biến mỗi đoạn thành một cặp số có thể lấy nhanh, nhưng người dùng phải hiểu rõ xác suất va chạm.

Vì sao so sánh xâu con trở thành nút thắt?

Giả sử một văn bản dài n có hàng trăm nghìn câu hỏi: đoạn [l1,r1) có giống đoạn [l2,r2) hay không. Cắt hai đoạn rồi so từng byte cho đáp án chắc chắn, nhưng một câu hỏi có thể tốn O(n). Rolling Hash chuẩn bị mã tiền tố để lấy “dấu vân tay” của mỗi đoạn trong O(1). Đổi lại, dấu vân tay là bằng chứng xác suất; hai đoạn khác nhau vẫn có khả năng rất nhỏ cho cùng mã.

Ý chính

Rolling Hash phù hợp khi cần rất nhiều phép so sánh trên xâu tĩnh. Nếu bài buộc đúng tuyệt đối, hãy xác minh các ứng viên bằng so sánh ký tự hoặc chọn KMP, Z-function, suffix array tùy loại truy vấn.

Rolling Hash: s = "abracadabra" · Khớp [0, 4) và [7, 11) a b r a c a d a b r a Đoạn [0, 4) = "abra" h[4] - h[0] · p[4] (mod M) Đoạn [7, 11) = "abra" h[11] - h[7] · p[4] (mod M) get(l, r) = (h[r] - h[l] · p[r - l]) mod M trong O(1)
Rolling Hash: "abracadabra" [0, 4) = "abra" · [7, 11) = "abra" Cùng cặp mã băm → Khớp [0, 3) = "abr" · [3, 6) = "aca" Khác mã băm → Loại ngay O(1) Công thức tách đoạn [l, r) (h[r] - h[l] · p[r - l]) mod M Dựng O(n) · Hỏi đoạn O(1)
Hình 1. Tách mã băm đoạn [l, r) từ mảng tiền tố h[] trên xâu "abracadabra".

Xây mã polynomial từ trái sang phải

Gọi giá trị byte ở vị trí i là x[i], cộng 1 để không biến byte 0 thành phần tử vô hình. Chọn cơ số B và modulo nguyên tố M. Tiền tố được dựng bởi h[i+1] = (h[i] * B + x[i]) mod M; đồng thời p[i+1] = p[i] * B mod M. Như vậy h[i] đại diện đúng i byte đầu và mọi phép nhân lũy thừa đã có sẵn.

Mã đoạn nửa mở [l,r) là h[r] - h[l] * p[r-l], lấy modulo rồi cộng M nếu âm. Phép trừ loại phần đứng trước l; phép nhân dịch nó sang đúng bậc. Hai đoạn chỉ đáng so khi có cùng độ dài. Bản mẫu tính công thức hai lần với M1=1.000.000.007 và M2=1.000.000.009, cùng cơ số 911.382.323, rồi so cặp kết quả.

Ví dụ abracadabra có [0,4) và [7,11) đều là abra. Hai thành phần hash bằng nhau; phép string.compare cuối cùng xác nhận hai lát ký tự thật sự trùng. Với [0,3) là abr và [3,6) là aca, cặp hash khác nên có thể kết luận khác ngay. Chương trình in hai cột: cột đầu là kết luận từ hash kép, cột sau là kết luận đã xác minh tuyệt đối.

Va chạm không phải lỗi cài đặt

Modulo ép vô số xâu vào hữu hạn mã nên va chạm tồn tại theo nguyên lý ngăn kéo. Hai modulo làm xác suất va chạm tình cờ nhỏ hơn rất nhiều nhưng không biến hash thành chứng minh toán học. Đối thủ có thể tạo dữ liệu có chủ đích nếu biết cơ số và modulo: với cơ số cố định 911.382.323 của bản mẫu, hai xâu chỉ gồm chữ a và b, dài 4.096 ký tự, đã đủ để trùng cả cặp mã. Vì thế ở kỳ thi cho phép hack (như Codeforces), hãy chọn cơ số ngẫu nhiên mỗi lần chạy, ví dụ lấy từ bộ sinh số ngẫu nhiên khởi tạo theo đồng hồ; còn hệ thống bảo mật thì không được dùng kiểu băm này thay hàm băm mật mã.

Trong bài thi thông thường, hash kép thường được chấp nhận để lọc ứng viên. Với yêu cầu chắc chắn, ta dùng cặp hash để bỏ nhanh phần lớn trường hợp, sau đó so trực tiếp những cặp còn lại. Khi tìm mẫu, số vị trí khớp thật thường ít nên phần xác minh rẻ; nhưng ở ca xấu như văn bản aaa…a và mẫu aa…a, gần như mọi vị trí đều khớp thật và tổng chi phí xác minh lên tới O(n·m). Đổi lại, độ đúng không còn phụ thuộc may rủi.

Cài đặt không vướng chỉ số

Đầu vào của mẫu dùng nguyên dòng nên giữ được khoảng trắng. Chỉ số là 0-based và đoạn là [l,r). Kích thước các mảng bằng n+1, trong đó phần tử 0 mô tả tiền tố rỗng. Hàm get(l,r) không tạo xâu con, do đó bước hash vẫn O(1). Hàm equal kiểm độ dài trước, so cặp mã, rồi mới gọi so sánh chính xác.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Hash2 {
    static constexpr long long M1=1000000007, M2=1000000009, B=911382323;
    string s; vector<long long> h1,h2,p1,p2;
    explicit Hash2(string text):s(move(text)),h1(s.size()+1),h2(s.size()+1),p1(s.size()+1,1),p2(s.size()+1,1){
        for(size_t i=0;i<s.size();++i){
            long long x=(unsigned char)s[i]+1;
            h1[i+1]=(h1[i]*B+x)%M1; h2[i+1]=(h2[i]*B+x)%M2;
            p1[i+1]=p1[i]*B%M1; p2[i+1]=p2[i]*B%M2;
        }
    }
    pair<long long,long long> get(int l,int r) const {
        long long a=(h1[r]-h1[l]*p1[r-l])%M1; if(a<0)a+=M1;
        long long b=(h2[r]-h2[l]*p2[r-l])%M2; if(b<0)b+=M2;
        return {a,b};
    }
    pair<bool,bool> equal(int l1,int r1,int l2,int r2) const {
        bool hash_equal=(r1-l1==r2-l2 && get(l1,r1)==get(l2,r2));
        bool exact=hash_equal && s.compare(l1,r1-l1,s,l2,r2-l2)==0;
        return {hash_equal,exact};
    }
};
int main(){
    string s="abracadabra"; int q=2;
    if(getline(cin,s) && cin>>q){} else {s="abracadabra";q=2;cin.clear();}
    Hash2 hs(s);
    if(s=="abracadabra" && q==2 && cin.peek()==EOF){
        for(auto x:vector<vector<int>>{{0,4,7,11},{0,3,3,6}}){auto [h,e]=hs.equal(x[0],x[1],x[2],x[3]);cout<<h<<' '<<e<<'\n';}
    } else for(int i=0,l1,r1,l2,r2;i<q;++i){cin>>l1>>r1>>l2>>r2;auto [h,e]=hs.equal(l1,r1,l2,r2);cout<<h<<' '<<e<<'\n';}
}

Tiền xử lý tốn O(n) thời gian và O(n) bộ nhớ. Một lần lấy hash kép tốn O(1). Nếu bật xác minh ký tự, trường hợp mã bằng nhau tốn thêm O(r-l); cần ghi rõ phần này thay vì tuyên bố mọi kết luận đều chắc chắn trong O(1).

Học cùng giảng viên

Chủ đề này nằm trong Buổi 09 - KMP, Z-function, Trie & Rolling Hash của Tài năng lập trình. Xem đề cương

Bốn lỗi làm đáp án sai âm thầm

  • Không đưa hiệu âm về [0,M): C++ giữ phần dư âm, khiến hai biểu thức tương đương có biểu diễn khác.
  • Dùng char có dấu: byte trên 127 có thể thành số âm; bản C++ chuyển sang unsigned char trước khi cộng 1.
  • So hai mã mà bỏ độ dài: cùng giá trị số không nói hai đa thức có cùng số hệ số.
  • Tạo substr trong từng truy vấn: kết quả vẫn đúng nhưng vô tình đưa chi phí tuyến tính trở lại.
Cẩn thận

Đừng chọn cơ số 0, 1 hoặc quá nhỏ so với bảng chữ cái. Cũng không được dùng Rolling Hash để lưu mật khẩu; đây là băm đa thức phục vụ thuật toán xâu, không phải hàm dẫn xuất mật khẩu.

Cách tự kiểm tra cài đặt Rolling Hash

Để kiểm tra công thức lấy mã đoạn [l, r) có bị lệch chỉ số hay dư âm hay không, bạn nên viết một hàm đối chiếu đơn giản: cắt trực tiếp hai đoạn s[l1..r1) và s[l2..r2) rồi so sánh từng ký tự. Hãy thử các trường hợp dễ lộ lỗi nhất: hai đoạn giống hệt nhau ở đầu và cuối xâu, hai đoạn khác nhau chỉ ở ký tự cuối, đoạn có ký tự lặp liên tiếp, đoạn chứa khoảng trắng và đoạn có độ dài bằng toàn bộ xâu. Các ca nhỏ này không nhằm chứng minh hàm băm không bao giờ va chạm, mà giúp bạn chắc chắn công thức nhân lũy thừa, phép lấy dư dương và quy ước nửa mở [l, r) đã khớp hoàn toàn.

Bạn cũng có thể sinh ngẫu nhiên các xâu ngắn từ bảng chữ cái nhỏ {a, b, c}, liệt kê mọi cặp đoạn cùng độ dài và so sánh kết quả của hàm get với phép cắt xâu trực tiếp. Nếu cặp mã băm bằng nhau nhưng hai đoạn ký tự thực tế khác nhau, bạn vừa quan sát được một ca va chạm; khi đó bước xác minh ký tự (cột thứ hai của kết quả) vẫn giữ cho kết quả cuối cùng chính xác.

Mở rộng từ bộ khung này

Để tìm mẫu, tính hash mẫu rồi quét các đoạn cùng độ dài trong văn bản. Để tìm tiền tố chung dài nhất của hai hậu tố, dùng tìm kiếm nhị phân trên độ dài và get. Để kiểm đối xứng, dựng thêm hash của xâu đảo và chuyển đúng tọa độ. Đếm xâu con phân biệt cần lưu mã kèm độ dài; chỉ lưu một số hash có thể khiến hai đoạn khác độ dài bị nhận nhầm là một.

Bảng chạy tay một truy vấn hash

Với xâu abca, hãy dựng lần lượt h[0], h[1], ..., h[4] bằng một modulo nhỏ như 101 để dễ bấm máy. Khi lấy đoạn [1,3) là bc, viết riêng hai vế h[3] và h[1] * p[2], rồi chuẩn hóa hiệu về số không âm. Làm lại trực tiếp từ hai ký tự b, c; hai kết quả phải bằng nhau.

Câu cần kiểm Dữ liệu nhỏ nên thử Kết quả mong đợi
Hai đoạn giống nhau abracadabra, [0,4) và [7,11) hash kép bằng, xác minh đúng
Cùng độ dài nhưng khác [0,3) và [3,6) ít nhất một hash khác
Đoạn rỗng [2,2) so với [5,5) cùng mã 0
Có khoảng trắng a b a, so [1,2) với [3,4) (hai dấu cách) hash kép bằng, xác minh đúng; đọc nguyên dòng nên không mất dấu cách

Khi sửa cơ số hoặc modulo, chạy lại toàn bộ bảng. Nếu hash bằng nhưng phép so ký tự báo khác, đó là va chạm hợp lệ về toán học; chương trình cần giữ bước xác minh nếu đề đòi kết quả tuyệt đối.

Chọn giữa Hash, KMP và Z

Rolling Hash mạnh nhất khi xâu đứng yên và câu hỏi thay đổi theo nhiều cặp đoạn. KMP thích hợp khi có một mẫu cần quét qua văn bản, đặc biệt khi dữ liệu đến theo luồng. Z-function thuận tiện khi cần biết độ khớp với tiền tố tại mọi vị trí. Cả ba đều có thể tìm mẫu, nhưng thông tin tiền xử lý phục vụ các biến thể khác nhau.

Nếu chỉ có một lần so hai đoạn, cắt và so trực tiếp thường rõ hơn. Nếu phải trả lời hàng trăm nghìn truy vấn LCP giữa các hậu tố, hash kết hợp tìm kiếm nhị phân là lựa chọn tự nhiên. Nếu đề không chấp nhận xác suất, suffix array cùng LCP, KMP hoặc phép xác minh trực tiếp sẽ an toàn hơn.

Một cách luyện tốt là giải cùng bài tìm mẫu bằng ba phương pháp, rồi ghi lại hợp đồng đúng của từng bản. Hash cần cơ số, modulo và chính sách va chạm; KMP cần mảng pi của mẫu; Z cần ký tự phân cách an toàn. Việc so sánh này giúp chọn công cụ theo dữ liệu, không theo tên thuật toán vừa học.

Luyện ngay trên Big-O Coding

Ba bài dưới đây luyện đúng băm xâu: tìm mẫu, đếm xâu con phân biệt dài K, và tìm xâu con chung dài nhất bằng băm kết hợp tìm kiếm nhị phân.

Câu hỏi thường gặp

Một modulo có đủ không?

Đủ khi chỉ so ít cặp: với M khoảng 10^9, xác suất hai xâu khác nhau trùng mã chỉ cỡ 1/M. Nhưng khi phải so rất nhiều mã với nhau, chẳng hạn đếm xâu con phân biệt với khoảng một triệu mã, thì gần như chắc chắn có va chạm (nghịch lý ngày sinh); khi đó dùng hai modulo, tương đương M khoảng 10^18. Khi cần tuyệt đối, vẫn phải xác minh ký tự.

Có thể cập nhật một ký tự không?

Mảng tiền tố tĩnh không hỗ trợ thuận tiện. Có thể đặt hash vào Fenwick hoặc Segment Tree và quản lý trọng số lũy thừa, nhưng công thức ghép phải nhất quán.

Vì sao không dùng std::hash<string>?

std::hash không cung cấp công thức tách hash của xâu con từ hai tiền tố, nên không giải mục tiêu truy vấn đoạn O(1).

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483