Hash xâu (String Hashing)

Hash xâu (string hashing) biến mỗi xâu thành một số nguyên sao cho hai xâu bằng nhau luôn có cùng số, còn hai xâu khác nhau thì gần như chắc chắn có số khác nhau. Sau $O(n)$ tiền xử lý, ta lấy được hash của bất kỳ xâu con nào trong $O(1)$, nên phép so sánh hai xâu con độ dài $L$ tốn $O(1)$ thay vì $O(L)$. Từ một công cụ duy nhất đó ta giải được tìm mẫu (Rabin-Karp), tiền tố chung dài nhất của hai hậu tố, so sánh thứ tự từ điển, đếm xâu con phân biệt, kiểm tra palindrome, xâu con lặp dài nhất, và cả các bài có cập nhật ký tự (kết hợp cây Fenwick). Cái giá phải trả: thuật toán là ngẫu nhiên, có xác suất sai, và trang này dành một phần lớn để giải thích cách giữ xác suất đó nhỏ tới mức bỏ qua được.

Ý tưởng / Trực giác

Hash đa thức: đọc xâu như một số trong hệ cơ số $B$

Gán mỗi ký tự một mã số dương (ví dụ mã ASCII, hoặc a = 1, b = 2, ...). Chọn cơ số $B$ và modulo $M$. Hash của xâu $s=s_0{s}_1\dots s_{L-1}$ là

$$H(s)=(s_0{B}^{L-1}+s_1{B}^{L-2}+\cdots +s_{L-2}B+s_{L-1})modM.$$

Nếu $B$ lớn hơn mọi mã ký tự và không lấy modulo, đây đúng là giá trị của xâu khi đọc như một số trong hệ cơ số $B$: hai xâu cùng độ dài bằng nhau khi và chỉ khi hai số bằng nhau. Với $B=10$ và a = 1, b = 2, c = 3, xâu abcab chính là số $12312$. Vấn đề duy nhất là số này có $L$ chữ số, quá lớn để lưu, nên ta lấy modulo $M$ và chấp nhận rằng hai xâu khác nhau có thể (hiếm khi) cho cùng phần dư. Hiện tượng đó gọi là đụng độ (collision).

Hash tiền tố và hash xâu con trong $O(1)$

Gọi $h[i]$ là hash của tiền tố độ dài $i$ (tức $s_0\dots s_{i-1}$), và $p[i]=B^{i}modM$:

$$h[0]=0,h[i+1]=h[i]·B+s_i,p[0]=1,p[i+1]=p[i]·B(\text{mod }M).$$

Hash của xâu con nửa mở $s[l..r)$ (độ dài $r-l$) là

$$\boxed{H(s[l..r))=h[r]-h[l]·B^{r-l}\left(\mathrm{mod}M\right)}$$

Vì sao đúng. Khai triển $h[r]$ thành hai phần: các ký tự $s_0\dots s_{l-1}$ và các ký tự $s_l\dots s_{r-1}$.

$$h[r]=\underset{=h[l]}{\underbrace{(s_0{B}^{l-1}+\cdots +s_{l-1})}}·B^{r-l}+\underset{=H(s[l..r))}{\underbrace{(s_l{B}^{r-l-1}+\cdots +s_{r-1})}}.$$

Mỗi lần nhân $B$ ở bước đệ quy là "dịch trái một chữ số"; sau khi đọc thêm $r-l$ ký tự, phần tiền tố $h[l]$ đã bị dịch trái đúng $r-l$ chữ số. Trừ nó đi thì còn lại đúng phần đuôi. Trong hệ thập phân: tiền tố $123$, cả xâu $12312$, bỏ $123·{10}^2=12300$ còn $12$, đúng là ab.

Nhờ công thức này, mọi thao tác "hai xâu con này có bằng nhau không?" trở thành so sánh hai số nguyên.

Chọn cơ số và modulo

• Modulo lớn, nguyên tố. Khi $M$ nguyên tố, hash của hai xâu khác nhau cùng độ dài $L$ trùng nhau khi và chỉ khi $B$ là nghiệm của đa thức hiệu $\sum (s_i-t_i)x^{L-1-i}$ (bậc không quá $L-1$, khác đa thức $0$) trên ${\mathbb{Z}}_M$. Đa thức bậc $\le L-1$ có không quá $L-1$ nghiệm, nên nếu $B$ chọn ngẫu nhiên đều trong $[0,M)$ thì

$$Pr[\text{đụng độ một cặp}]\le \frac{L-1}{M}.$$

• Cơ số ngẫu nhiên. Cận trên đúng với mọi cặp xâu, kể cả do người ra đề cố tình chọn, chỉ khi $B$ được chọn ngẫu nhiên lúc chạy. Cơ số cố định quen thuộc ($31$, $131$, $311$) kèm modulo cố định thì người ra đề có thể dựng sẵn hai xâu đụng độ.
• Modulo $2^{61}-1$. Đây là số nguyên tố Mersenne, đủ lớn để xác suất đụng độ gần như bằng $0$, và phép lấy dư rất nhanh: vì $2^{61}\equiv 1$, một tích $x<2^{122}$ viết thành $x=a·2^{61}+b$ thì $x\equiv a+b$. Tích hai số $<2^{61}$ cần kiểu 128 bit (__int128 trong GCC).

Nghịch lý ngày sinh: vì sao một modulo ${10}^9+7$ không đủ

Xác suất $\frac{1}{M}$ cho một cặp nghe rất nhỏ, nhưng các bài thường so sánh rất nhiều cặp cùng lúc. Nếu ta có $k$ giá trị hash (ví dụ hash của mọi xâu con độ dài cố định, đưa vào một tập để đếm), số cặp là $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\approx \frac{k^2}{2}$ và số cặp đụng độ kỳ vọng xấp xỉ

$$\frac{k^2}{2M}.$$

Đây là nghịch lý ngày sinh: chỉ cần 23 người là xác suất có hai người trùng ngày sinh đã vượt 50%, vì số cặp tăng theo bình phương.

Lưu ý: bảng trên (và ước lượng $\frac{n}{M}$ cho Rabin-Karp bên dưới) là ước lượng kinh nghiệm, coi hash như một hàm ngẫu nhiên (mỗi cặp đụng độ với xác suất $\frac{1}{M}$). Điều chứng minh được với cơ số ngẫu nhiên chỉ là cận $\frac{L-1}{M}$ cho mỗi cặp ở mục trước, lớn hơn $\frac{1}{M}$ tới $L-1$ lần; trong thực tế hash đa thức với cơ số ngẫu nhiên hành xử gần với ước lượng kinh nghiệm.

Quy tắc thực hành: không gian hash cần lớn hơn nhiều so với bình phương số giá trị phải phân biệt. Một modulo cỡ ${10}^9$ chỉ an toàn khi ta so sánh ít cặp (ví dụ Rabin-Karp một mẫu: mỗi vị trí so với một giá trị đích, tổng cộng $n$ phép so sánh, xác suất sai tổng $\approx \frac{n}{M}$). Khi đưa nhiều hash vào tập hợp, sắp xếp hay bảng băm, hãy dùng double hash (hai modulo $\approx {10}^9$ với hai cơ số ngẫu nhiên, ghép thành cặp) hoặc modulo $2^{61}-1$.

Vì sao hash tràn số tự nhiên (mod $2^{64}$) bị phá

Nhiều người dùng unsigned long long và để phép nhân tràn tự nhiên, tức lấy modulo $2^{64}$. Nhanh, nhưng $2^{64}$ không nguyên tố và có thể bị phá với mọi cơ số:

• Cơ số chẵn: $B^{64}\equiv 0\left(\mathrm{mod}{2}^{64}\right)$, nên mọi ký tự cách cuối xâu từ 64 vị trí trở lên đều không ảnh hưởng tới hash.
• Cơ số lẻ: dùng xâu Thue-Morse. Đặt $S_0=$ a, $T_0=$ b, và $S_{k+1}=S_k{T}_k$, $T_{k+1}=T_k{S}_k$ ($T_k$ là $S_k$ với a và b đổi cho nhau). Gọi $D_k=H(S_k)-H(T_k)$, độ dài $|S_k|=2^k$:

$$D_{k+1}=(H(S_k)B^{2^k}+H(T_k))-(H(T_k)B^{2^k}+H(S_k))=D_k·(B^{2^k}-1).$$

Suy ra $D_k=\pm {\prod }_{i=0}^{k-1}(B^{2^i}-1)$. Với $B$ lẻ, $B-1$ chia hết cho $2$, còn $B^{2^i}-1$ chia hết cho $2^{i+2}$ khi $i\ge 1$. Tổng số mũ của $2$ là $1+{\sum }_{i=1}^{k-1}(i+2)$, bằng $64$ khi $k=10$. Vậy hai xâu khác nhau độ dài $1024$ là $S_{10}$ và $T_{10}$ luôn có cùng hash mod $2^{64}$ với mọi cơ số lẻ, dù cơ số được chọn ngẫu nhiên.

Các bài hash trên các OJ lớn thường có sẵn test dạng này. Kết luận: dùng modulo nguyên tố (một modulo lớn hoặc hai modulo), đừng dùng tràn số tự nhiên.

Ví dụ chạy tay

Hash tiền tố và Rabin-Karp

Tìm mẫu $p=$ aba trong $t=$ abacabab. Để dễ nhìn, dùng $B=10$, a = 1, b = 2, c = 3 và không lấy modulo (số nhỏ). Hash của mẫu: $H(p)=121$.

 i        :  0  1  2  3  4  5  6  7
 t[i]     :  a  b  a  c  a  b  a  b
 mã       :  1  2  1  3  1  2  1  2

 h[0..8]  :  0, 1, 12, 121, 1213, 12131, 121312, 1213121, 12131212
 p[3] = 10^3 = 1000

Trượt cửa sổ độ dài 3, mỗi cửa sổ tính trong $O(1)$ bằng $h[i+3]-h[i]·1000$:

 i   cửa sổ   h[i+3] - h[i]*1000              hash   = 121 ?
 0   [aba]    121      - 0*1000              = 121    khớp
 1   [bac]    1213     - 1*1000              = 213
 2   [aca]    12131    - 12*1000             = 131
 3   [cab]    121312   - 121*1000            = 312
 4   [aba]    1213121  - 1213*1000           = 121    khớp
 5   [bab]    12131212 - 12131*1000          = 212

 t:  a b a c a b a b
     [===]   [===]       mẫu xuất hiện tại i = 0 và i = 4

Trong cài đặt thật mọi phép tính lấy modulo $M$ và $B$ ngẫu nhiên, nhưng cơ chế y hệt.

LCP hai hậu tố và so sánh từ điển

Vẫn với $t=$ abacabab, so sánh hậu tố tại $0$ (abacabab) và hậu tố tại $4$ (abab). Tiền tố chung dài nhất (LCP, longest common prefix) có tính đơn điệu: nếu hai hậu tố khớp $x$ ký tự đầu thì cũng khớp mọi độ dài nhỏ hơn. Vì vậy chặt nhị phân độ dài, mỗi bước so hai hash:

 lo = 0, hi = min(8-0, 8-4) = 4
 mid = 2 : "ab"   vs "ab"     hash bằng  -> lo = 2
 mid = 3 : "aba"  vs "aba"    hash bằng  -> lo = 3
 mid = 4 : "abac" vs "abab"   hash khác  -> hi = 3
 LCP = 3

 a b a c a b a b        vị trí 0 + 3 = 3: 'c'
 a b a b                vị trí 4 + 3 = 7: 'b'
 ^ ^ ^ x                'b' < 'c'  nên hậu tố tại 4 nhỏ hơn

Biết LCP $=k$ thì thứ tự từ điển quyết định bởi ký tự thứ $k$ của hai xâu (hoặc xâu nào hết trước thì nhỏ hơn). Đây là phép so sánh $O(\log n)$ dùng được làm hàm so sánh cho sort khi sắp các hậu tố: với hai hậu tố tại $a$ và $b$ (độ dài $n-a$ và $n-b$ có thể khác nhau), tính $k=$ lcp(H, n, a, b); nếu $k$ chạm hết hậu tố ngắn hơn (tức $a+k=n$ hoặc $b+k=n$) thì hậu tố ngắn hơn là nhỏ hơn, ngược lại so s[a + k] với s[b + k]. Hàm compareSub trong phần cài đặt chỉ xử lý trường hợp hai xâu con cùng độ dài len, nên muốn so hai hậu tố thì dùng lcp cộng quy tắc này.

Cài đặt

Hash modulo $2^{61}-1$ với cơ số ngẫu nhiên (C++)

Chương trình dưới đây gồm lõi StringHash và ba ứng dụng: tìm mọi vị trí xuất hiện (Rabin-Karp), LCP của hai hậu tố, so sánh hai xâu con theo thứ tự từ điển.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

// Polynomial hash modulo the Mersenne prime 2^61 - 1
const ull MOD = (1ULL << 61) - 1;

ull mulmod(ull a, ull b) {
    __uint128_t p = (__uint128_t)a * b;
    ull r = (ull)(p & MOD) + (ull)(p >> 61);   // 2^61 = 1 (mod MOD)
    if (r >= MOD) r -= MOD;
    return r;
}

// random base in [256, MOD - 1], chosen once per run
const ull BASE = []() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return rng() % (MOD - 256) + 256;
}();

struct StringHash {
    vector<ull> h, pw;   // h[i] = hash of s[0..i-1], pw[i] = BASE^i
    StringHash(const string& s) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = (mulmod(h[i], BASE) + (unsigned char)s[i]) % MOD;
            pw[i + 1] = mulmod(pw[i], BASE);
        }
    }
    // hash of s[l..r) (half-open), O(1)
    ull get(int l, int r) const {
        ull sub = mulmod(h[l], pw[r - l]);
        return h[r] >= sub ? h[r] - sub : h[r] + MOD - sub;
    }
};

// Rabin-Karp: all start positions of p in t
vector<int> findAll(const string& t, const string& p) {
    vector<int> res;
    if (p.size() > t.size()) return res;
    StringHash ht(t), hp(p);
    ull target = hp.get(0, p.size());
    int m = p.size();
    for (int i = 0; i + m <= (int)t.size(); i++)
        if (ht.get(i, i + m) == target) res.push_back(i);
    return res;
}

// LCP of s[a..) and s[b..) by binary search on length
int lcp(const StringHash& H, int n, int a, int b) {
    int lo = 0, hi = n - max(a, b);            // answer in [lo, hi]
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (H.get(a, a + mid) == H.get(b, b + mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

// compare s[a..a+len) and s[b..b+len): returns -1, 0 or 1
int compareSub(const string& s, const StringHash& H, int a, int b, int len) {
    int k = min(lcp(H, s.size(), a, b), len);
    if (k == len) return 0;
    return s[a + k] < s[b + k] ? -1 : 1;
}

int main() {
    string t = "abacabab";
    for (int x : findAll(t, "aba")) printf("%d ", x);   // 0 4
    puts("");
    StringHash H(t);
    printf("%d\n", lcp(H, t.size(), 0, 4));             // 3
    printf("%d\n", compareSub(t, H, 0, 4, 4));          // 1  ("abac" > "abab")
    printf("%d\n", compareSub(t, H, 4, 0, 3));          // 0  ("aba" == "aba")
}

Ghi chú cài đặt:

• Mã ký tự dùng thẳng (unsigned char)s[i] (luôn $\ge 1$ với ký tự in được) và $B\ge 256$, nên không có ký tự nào mang mã $0$ (xem mục ⚠️).
• get trả về giá trị trong $[0,M)$ mà không cần phép % có dấu: nếu $h[r]<$ phần bị trừ thì cộng thêm $M$.
• Muốn so sánh xâu con của hai xâu khác nhau (ví dụ mẫu và văn bản), dựng hai StringHash riêng; chúng dùng chung BASE toàn cục nên hash so sánh được với nhau.

Các ứng dụng khác trên cùng lõi

Khối dưới đây chép vào sau struct StringHash (trước main) của chương trình trên.

// ---- palindrome check with forward and reversed hashes
struct PalindromeChecker {
    int n;
    StringHash fwd, rev;
    PalindromeChecker(const string& s)
        : n(s.size()), fwd(s), rev(string(s.rbegin(), s.rend())) {}
    // is s[l..r] (inclusive) a palindrome?
    bool isPal(int l, int r) const {
        // s[l..r] reversed is rev[n-1-r .. n-1-l]
        return fwd.get(l, r + 1) == rev.get(n - 1 - r, n - l);
    }
};

// ---- number of distinct substrings of length k
int countDistinct(const StringHash& H, int n, int k) {
    vector<ull> v;
    for (int i = 0; i + k <= n; i++) v.push_back(H.get(i, i + k));
    sort(v.begin(), v.end());
    return unique(v.begin(), v.end()) - v.begin();
}

// ---- longest substring occurring at least twice: returns {length, start}
pair<int, int> longestRepeat(const string& s) {
    int n = s.size();
    StringHash H(s);
    // start of a repeated substring of length len, or -1
    auto check = [&](int len) -> int {
        vector<pair<ull, int>> v;
        for (int i = 0; i + len <= n; i++) v.push_back({H.get(i, i + len), i});
        sort(v.begin(), v.end());
        for (size_t i = 1; i < v.size(); i++)
            if (v[i].first == v[i - 1].first) return v[i].second;
        return -1;
    };
    int lo = 0, hi = n - 1, pos = -1;   // length n can never repeat
    while (lo < hi) {                   // monotone: repeat of len => repeat of len-1
        int mid = (lo + hi + 1) / 2;
        int p = check(mid);
        if (p >= 0) { lo = mid; pos = p; } else hi = mid - 1;
    }
    return {lo, pos};                   // lo = 0 means no repeated substring
}

Ví dụ với s = "cabababc": isPal(1, 5) (xâu ababa) trả true, countDistinct(H, 8, 2) trả $4$ (ca, ab, ba, bc), longestRepeat trả độ dài $4$ ứng với abab (xuất hiện tại vị trí $1$ và $3$, đánh số từ $0$, chồng lên nhau).

Kiểm tra palindrome: xâu con $s[l..r]$ đọc ngược chính là đoạn $[n-1-r,n-1-l]$ của xâu đảo $\bar{s}$. Palindrome nghĩa là đọc xuôi bằng đọc ngược, nên chỉ cần so hash xuôi với hash của đoạn tương ứng trên xâu đảo.

Xâu con lặp dài nhất: nếu có xâu độ dài $L$ xuất hiện hai lần thì tiền tố độ dài $L-1$ của nó cũng xuất hiện hai lần, nên tính chất "có xâu lặp độ dài $L$" đơn điệu và chặt nhị phân được. Cùng khuôn "chặt nhị phân độ dài + kiểm tra bằng hash" giải xâu con chung dài nhất của hai xâu $A$, $B$: với độ dài $L$, đưa hash mọi xâu con độ dài $L$ của $A$ vào một tập, rồi kiểm tra xem có xâu con độ dài $L$ nào của $B$ nằm trong tập không.

Hash có cập nhật điểm: Fenwick

Khi xâu bị sửa ký tự giữa các truy vấn, mảng hash tiền tố phải dựng lại $O(n)$. Cách khắc phục: viết hash dưới dạng tổng, rồi đặt tổng đó vào cây Fenwick. Đặt $F={\sum }_{i=l}^r{s}_i{B}^i$ (mỗi ký tự nhân với lũy thừa theo vị trí tuyệt đối). Sửa $s_k$ chỉ đổi một số hạng, tức một phép cộng điểm trên Fenwick. Hai đoạn cùng độ dài bắt đầu ở $l_1$, $l_2$ bằng nhau khi $F_1·B^{l_2}=F_2·B^{l_1}$ (nhân chéo để đưa về cùng "độ dịch", khỏi cần nghịch đảo modulo).

Chương trình dưới đây giải bài "sửa ký tự và hỏi đoạn $[a,b]$ có phải palindrome": thêm một Fenwick thứ hai lưu $s_i{B}^{n-1-i}$ (lũy thừa theo vị trí tính từ cuối). Gọi $R={\sum }_{i=a}^b{s}_i{B}^{n-1-i}$. Đoạn là palindrome khi và chỉ khi $s_{a+j}=s_{b-j}$ với mọi $j$. Nhân hai tổng với lũy thừa thích hợp để đưa về cùng số mũ, rồi đổi chỉ số $j=a+b-i$ trong tổng của $R$:

$$F·B^{n-1-b}=\sum _{i=a}^b{s}_i{B}^{n-1-b+i},R·B^a=\sum _{j=a}^b{s}_j{B}^{n-1-j+a}=\sum _{i=a}^b{s}_{a+b-i}{B}^{n-1-b+i}.$$

Hai tổng có cùng lũy thừa ở từng vị trí $i$, chỉ khác hệ số $s_i$ và $s_{a+b-i}$. Vì vậy (với xác suất đụng độ nhỏ như mọi hash đa thức) đoạn là palindrome khi và chỉ khi

$$F·B^{n-1-b}=R·B^a.$$

Mọi số mũ ở đây đều không âm, nên chỉ cần mảng lũy thừa pw, không cần nghịch đảo modulo.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
ull mulmod(ull a, ull b) {
    __uint128_t p = (__uint128_t)a * b;
    ull r = (ull)(p & MOD) + (ull)(p >> 61);
    if (r >= MOD) r -= MOD;
    return r;
}
ull addmod(ull a, ull b) { a += b; return a >= MOD ? a - MOD : a; }
ull submod(ull a, ull b) { return a >= b ? a - b : a + MOD - b; }

// Fenwick tree of values mod MOD (point add, prefix sum)
struct Fenwick {
    int n; vector<ull> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, ull v) { for (i++; i <= n; i += i & -i) t[i] = addmod(t[i], v); }
    ull sum(int i) const { ull s = 0; for (; i > 0; i -= i & -i) s = addmod(s, t[i]); return s; } // [0, i)
    ull range(int l, int r) const { return submod(sum(r + 1), sum(l)); }                           // [l, r]
};

int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    const ull BASE = rng() % (MOD - 256) + 256;
    int n, m;
    scanf("%d %d", &n, &m);
    static char buf[200005];
    scanf("%s", buf);
    string s = buf;
    vector<ull> pw(n + 1, 1);
    for (int i = 1; i <= n; i++) pw[i] = mulmod(pw[i - 1], BASE);
    // fwd stores s[i] * B^i, bwd stores s[i] * B^(n-1-i)
    Fenwick fwd(n), bwd(n);
    for (int i = 0; i < n; i++) {
        fwd.add(i, mulmod((unsigned char)s[i], pw[i]));
        bwd.add(i, mulmod((unsigned char)s[i], pw[n - 1 - i]));
    }
    while (m--) {
        int type; scanf("%d", &type);
        if (type == 1) {
            int k; char c; scanf("%d %c", &k, &c); k--;
            // remove old char, add new one
            fwd.add(k, MOD - mulmod((unsigned char)s[k], pw[k]));
            bwd.add(k, MOD - mulmod((unsigned char)s[k], pw[n - 1 - k]));
            s[k] = c;
            fwd.add(k, mulmod((unsigned char)c, pw[k]));
            bwd.add(k, mulmod((unsigned char)c, pw[n - 1 - k]));
        } else {
            int a, b; scanf("%d %d", &a, &b); a--; b--;
            // palindrome  <=>  F * B^(n-1-b) == R * B^a
            ull F = fwd.range(a, b), R = bwd.range(a, b);
            puts(mulmod(F, pw[n - 1 - b]) == mulmod(R, pw[a]) ? "YES" : "NO");
        }
    }
}

Với input 7 5 / aybabtu / 2 3 5 / 1 3 x / 2 3 5 / 1 5 x / 2 3 5, chương trình in YES NO YES (các đoạn bab, xab, xax).

Cách khác bằng segment tree: mỗi nút lưu hash của đoạn nó quản lý (theo định nghĩa gốc, không nhân vị trí tuyệt đối) cùng độ dài đoạn. Ghép nút trái $X$ với nút phải $Y$:

$$H(XY)=H(X)·B^{|Y|}+H(Y).$$

Truy vấn đoạn trả về trực tiếp hash chuẩn của đoạn, không cần nhân chéo. Cách này cũng hợp khi nút cần lưu thêm thông tin khác, hoặc khi có thao tác trên đoạn (ví dụ gán cả đoạn thành một ký tự: hash của $L$ ký tự $c$ là $c·(1+B+\cdots +B^{L-1})$, tính trước được).

Python

Python có số nguyên lớn nên phép nhân modulo $2^{61}-1$ không cần xử lý đặc biệt. Phù hợp để hiểu và cho $n$ tới khoảng ${10}^5$; với ${10}^6$ ký tự thì vòng lặp Python chậm, nên dùng C++.

import random

MOD = (1 << 61) - 1
BASE = random.randrange(256, MOD)


class StringHash:
    def __init__(self, s):
        n = len(s)
        self.h = [0] * (n + 1)   # h[i] = hash of s[:i]
        self.pw = [1] * (n + 1)  # pw[i] = BASE**i % MOD
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * BASE + ord(ch)) % MOD
            self.pw[i + 1] = self.pw[i] * BASE % MOD

    def get(self, l, r):
        """Hash of s[l:r] (half-open)."""
        return (self.h[r] - self.h[l] * self.pw[r - l]) % MOD


def find_all(t, p):
    """Rabin-Karp: start indices of p in t."""
    ht, hp = StringHash(t), StringHash(p)
    target, m = hp.get(0, len(p)), len(p)
    return [i for i in range(len(t) - m + 1) if ht.get(i, i + m) == target]


print(find_all("abacabab", "aba"))  # [0, 4]

Toán tử % của Python luôn trả số không âm với modulo dương, nên get không cần cộng thêm $M$.

Độ phức tạp

Hằng số của phép nhân modulo $2^{61}-1$ lớn hơn phép nhân 64 bit thường vài lần (một phép nhân 128 bit, vài phép dịch và cộng), nhưng thường không chậm hơn double hash (hai phép % cho mỗi bước) mà xác suất đụng độ lại nhỏ hơn.

⚠️ Lỗi thường gặp

• Một modulo cỡ ${10}^9$ khi so sánh nhiều cặp. Triệu chứng: sai ngẫu nhiên ở test lớn, chạy lại có khi đúng có khi sai. Nguyên nhân là nghịch lý ngày sinh: ${10}^5$ hash trong một tập với $M\approx {10}^9$ đã cho khoảng $5$ cặp đụng độ kỳ vọng. Cách tránh: modulo $2^{61}-1$ hoặc double hash.
• Tràn số tự nhiên mod $2^{64}$. Triệu chứng: sai đúng một test dù đã thử nhiều cơ số. Hai xâu Thue-Morse độ dài $1024$ luôn đụng độ với mọi cơ số lẻ, cơ số chẵn thì còn tệ hơn. Cách tránh: dùng modulo nguyên tố.
• Cơ số cố định, modulo cố định. Trên các bài có test chống hash (hoặc có phần "hack" như Codeforces), cặp $(B,M)$ quen thuộc như $(31,{10}^9+7)$ có thể đã bị dựng sẵn test đụng độ. Cách tránh: sinh $B$ ngẫu nhiên lúc chạy từ đồng hồ (chrono::steady_clock), không dùng rand() với seed cố định.
• Ký tự mang mã $0$. Với s[i] - 'a' thì a có mã $0$, nên a, aa, aaa đều có hash $0$. So hai xâu cùng độ dài thì không sao, nhưng khi đưa xâu con nhiều độ dài khác nhau vào cùng một tập (đếm mọi xâu con phân biệt) thì đụng độ chắc chắn. Cách tránh: dùng s[i] - 'a' + 1 hoặc mã ASCII, và/hoặc ghép độ dài vào khóa.
• Cơ số không lớn hơn mã ký tự. Với $B=2$ và mã $1.\mathrm{.3}$: ac $=1·2+3=5=2·2+1=$ ba, đụng độ ngay cả khi không lấy modulo. Cơ số phải lớn hơn mã ký tự lớn nhất; cơ số ngẫu nhiên lớn tự động thỏa.
• Số âm và tràn khi tính $h[r]-h[l]·B^{r-l}$. Với long long và modulo ${10}^9+7$, phép trừ cho số âm, % của C++ giữ dấu, nên phải cộng $M$ trước khi lấy dư. Với modulo $2^{61}-1$, tích hai số vượt 64 bit, bắt buộc dùng __int128 như mulmod ở trên; nhân thẳng a * b % MOD trên unsigned long long là sai.
• Lệch chỉ số giữa đoạn đóng và nửa mở. get(l, r) ở đây là nửa mở $[l,r)$. Gọi get(l, r) cho đoạn đóng $[l,r]$ sẽ thiếu ký tự cuối. Chọn một quy ước và giữ nó trong toàn bộ bài; khi kiểm tra palindrome, công thức vị trí trên xâu đảo cũng đổi theo quy ước.
• Chặt nhị phân khi tính chất không đơn điệu. "Có xâu con lặp độ dài $L$" đơn điệu, nhưng "có đoạn $XX$ (một xâu lặp liền hai lần) với $|X|=L$" thì không: abab có đoạn với $L=2$ nhưng không có với $L=1$. Trước khi chặt nhị phân phải chứng minh tính đơn điệu; nếu không có, phải thử mọi $L$.
• Hash bằng nhau chưa chắc xâu bằng nhau. Hash khác nhau thì chắc chắn khác nhau, còn hash bằng nhau chỉ "gần như chắc chắn" bằng nhau. Khi cần chắc tuyệt đối và số lần khớp ít (ví dụ in ra vị trí khớp đầu tiên), có thể so thêm trực tiếp $O(m)$ để xác nhận. Không làm vậy khi số lần khớp lớn (mẫu a trong aaaa...a), vì sẽ quay về $O(nm)$.
• Hash của hai xâu khác độ dài. Hash không mã hóa độ dài (xem lỗi mã $0$). Khi lưu hash vào map/set cùng lúc cho nhiều độ dài, dùng khóa là cặp (độ dài, hash).

Biến thể / Mở rộng

• So với thuật toán tất định. Tìm một mẫu trong văn bản thì KMP và Z-function cho kết quả chắc chắn đúng trong $O(n+m)$. Palindrome dài nhất có Manacher $O(n)$ (hash + chặt nhị phân chỉ đạt $O(n\log n)$). Sắp xếp hậu tố và LCP có Suffix Array. Hash thắng ở sự linh hoạt: so sánh hai đoạn bất kỳ, của nhiều xâu khác nhau, có cập nhật, hay trên cấu trúc 2 chiều, đều dùng cùng một công thức.
• Nhiều mẫu cùng độ dài. Đưa hash các mẫu vào một bảng băm, rồi trượt cửa sổ trên văn bản và tra bảng: $O(n+\sum |p_i|)$ kỳ vọng. Mẫu có độ dài khác nhau thì nhóm theo độ dài (có không quá $O(\sqrt{\sum |p_i|})$ độ dài khác nhau), hoặc dùng Aho-Corasick.
• Xoay vòng. Xét $s+s$: mọi phép xoay của $s$ là một xâu con độ dài $|s|$ của $s+s$. So sánh hai phép xoay theo thứ tự từ điển bằng LCP như trên cho phép xoay nhỏ nhất trong $O(n\log n)$.
• Hash 2 chiều. Với bảng ký tự, lấy hash từng đoạn hàng độ dài $w$ theo cơ số $B_1$, rồi coi $h$ hash hàng liên tiếp như một "xâu" và hash tiếp theo cột bằng cơ số $B_2$. Hash của mọi khối $h\times w$ tính trong $O(1)$ sau $O(MN)$ tiền xử lý.
• Khác đúng một vị trí. Hash thay đổi tuyến tính theo từng ký tự: đổi $s_i$ từ $c$ thành $c^{\prime }$ làm hash cộng thêm $(c^{\prime }-c)B^{L-1-i}$. Nhờ đó liệt kê mọi xâu khác $s$ đúng một vị trí mà không cần dựng lại từng xâu.

• Hash tập hợp (XOR/sum hashing). Khi thứ tự không quan trọng, gán mỗi giá trị phần tử một số ngẫu nhiên 64 bit $r(x)$, rồi cập nhật $O(1)$ khi thêm bớt phần tử:

  • Tập hợp (mỗi phần tử có hoặc không): lấy XOR các $r(x)$. Chỉ dùng cho tập, vì một phần tử xuất hiện số chẵn lần sẽ tự triệt tiêu ($r\oplus r=0$), nên $\{x,x\}$ và $\varnothing$ cho cùng hash.
  • Đa tập (đếm cả số lần xuất hiện): lấy tổng các $r(x)$ mod $2^{64}$; phần tử xuất hiện $c$ lần đóng góp $c·r(x)$.

  Đây là họ hàng của hash xâu, dùng cho các bài "hai đoạn có cùng tập (đa tập) phần tử không".

Bài tập luyện

Luyện kỹ thuật

• Khớp Xâu (strmatch) (Trung cấp) đếm số lần một mẫu xuất hiện trong văn bản tới ${10}^6$ ký tự: Rabin-Karp nguyên bản, so hash từng cửa sổ với hash của mẫu (cũng giải được bằng KMP hoặc Z-function để đối chiếu).
• Xâu con tốt (kbadsub) (Nâng cao) đếm xâu con phân biệt thỏa điều kiện với $|s|\le 1500$: đưa hash của tới khoảng ${10}^6$ xâu con nhiều độ dài vào một tập, nên một modulo cỡ ${10}^9$ chắc chắn đụng độ (khoảng vài trăm cặp theo nghịch lý ngày sinh), nếu có test chống hash thì tràn số $2^{64}$ cũng hỏng, và lỗi ký tự mã $0$ lộ ra.
• Khác đúng một vị trí (onediff) (Kỳ cựu) lưu hash các xâu trong bộ nhớ vào bảng băm, với mỗi truy vấn thử đổi từng ký tự và cập nhật hash trong $O(1)$ bằng số hạng $(c^{\prime }-c)B^{L-1-i}$.
• Truy Vấn Palindrome (palinq) (Kỳ cựu) sửa ký tự và hỏi đoạn có phải palindrome: đúng bài của chương trình Fenwick ở trên (hash xuôi và ngược có cập nhật điểm).
• Xâu Con Lặp Lại (repsubstr) (Chuyên gia) xâu con xuất hiện ít nhất hai lần dài nhất: chặt nhị phân độ dài, mỗi bước sắp hoặc đưa vào bảng băm hash mọi xâu con độ dài đó (đối chiếu với lời giải bằng Suffix Array + LCP).

Đề VOI

• Trao đổi thông tin (voi13_msg) (Kỳ cựu) VOI 2013: tìm bảng chữ nhật diện tích lớn nhất xuất hiện trong cả hai bảng ký tự. Cần một phép kiểm tra "có khối $h\times w$ chung không" bằng hash 2 chiều (hash đoạn hàng, rồi hash tiếp theo cột), và để ý số khối đưa vào bảng băm đủ nhiều để hash 32 bit bị đụng độ.
• Virus (voi17_virus) (Nâng cao) VOI 2017: hash không phải lời giải chính thức; nó chỉ giải được subtask $k_i=0$ (so hai nửa của đoạn $XX$), các subtask còn lại cần ý khác. Bài cũng là ví dụ điển hình cho bẫy "độ dài không đơn điệu, không chặt nhị phân được".
• Bài đăng (voi26_post) (Chuyên gia) VOI 2026: lời giải chính thức dùng segment tree, không dùng hash. Hash ở đây là hash tập hợp bằng XOR (không phải hash đa thức), một cách nhìn khác: thử tìm một đại lượng gắn với mỗi "vách" giữa hai bài liên tiếp sao cho điều kiện "đoạn toàn vẹn" trở thành "hai vách có cùng hash". Cách nhìn này giải thẳng subtask 4 (một truy vấn trên cả dãy) và subtask 5 khi kết hợp thuật toán Mo; subtask cuối cần thêm ý khác.