Hashing

Hash đa thức

Hãy xem một xâu như một số viết trong hệ cơ số $b$. Với a = 1, b = 2, c = 3 và cơ số 10, xâu abc là số 123, xâu cab là số 312; hai xâu bằng nhau khi và chỉ khi hai số bằng nhau. Nhưng số có $n$ chữ số cũng dài như xâu, nên ta lấy phần dư theo một số $M$:

Ở đây $s_i$ là giá trị số của ký tự thứ $i$ (mã ASCII, hoặc c - 'a' + 1), $b$ là cơ số, $M$ là modulo. Cách tính gọn là sơ đồ Horner: $H \leftarrow (H \cdot b + s_i) \bmod M$ với $i = 1, \dots, n$. Hai xâu bằng nhau thì hash bằng nhau, luôn luôn; nên hai hash khác nhau chứng minh được hai xâu khác nhau. Ngược lại, hai xâu khác nhau vẫn có thể trùng hash, gọi là va chạm (collision), không tránh hẳn được vì chỉ có $M$ giá trị hash. Giá trị ký tự phải $\ge 1$: nếu gán a bằng 0 thì a, aa, aaa đều có hash 0, giống chữ số 0 đứng đầu không đổi giá trị của một số.

Hash của xâu con. Giống tổng tiền tố (bài 02), dựng trước hash của mọi tiền tố, $h_0 = 0$ và $h_i = (h_{i-1} \cdot b + s_i) \bmod M$. Trong $h_r$, ký tự $s_j$ mang trọng số $b^{r-j}$, đúng trọng số mà hash của $s[l..r]$ cần; phần thừa là $s_1, \dots, s_{l-1}$, chính là $h_{l-1}$ bị đẩy sang trái $r - l + 1$ vị trí. Vậy

Xem trong hệ thập phân cho dễ thấy: với $s$ = abacab, các tiền tố là $0, 1, 12, 121, 1213, 12131, 121312$; đoạn $[3, 5]$ là aca, số của nó là $12131 - 12 \cdot 10^3 = 131$.

Trong hình, với $b = 10$ và $M$ lớn, hash đọc được như số thập phân. Đổi $l$, $r$ để lấy hash đoạn khác, hoặc đổi $b$, $M$.

Ta cần thêm mảng lũy thừa $\mathrm{pw}_k = b^k \bmod M$. Dựng cả hai mảng tốn $O(n)$, rồi mỗi đoạn lấy hash trong $O(1)$. Hai chỗ hay sai: phép trừ modulo có thể ra số âm nên phải cộng thêm $M$; và chỉ so hash của hai đoạn cùng độ dài. Khi một cửa sổ cố định độ dài $m$ trượt đi, ta cũng có thể cập nhật thẳng $H \leftarrow (H - s_i b^{m-1}) b + s_{i+m}$ (hash cuộn, rolling hash), nhưng mảng tiền tố làm được cùng việc và lấy được cả đoạn độ dài tùy ý.

Ví dụDấu Vân Tay Của Xâu

Đề. Cho xâu $s$ gồm $n \le 50$ chữ thường, $\mathrm{value}(a) = 1, \dots, \mathrm{value}(z) = 26$. In $H(s) = \sum_{i=0}^{n-1} \mathrm{value}(s_i) \cdot 31^i \bmod 1234567891$.

Lời giải. Đề viết đa thức theo chiều ngược với Horner: ký tự đầu mang lũy thừa thấp nhất. Cứ duyệt từ trái sang, giữ $p = 31^i \bmod M$ và cộng dần $\mathrm{value}(s_i) \cdot p$. Mọi giá trị giữ dưới $M$ ngay từ đầu; $p$ tới $1{,}2 \cdot 10^9$ nên nhân với 31 phải bằng ll, int đã tràn. Với abcde: $1 + 2 \cdot 31 + 3 \cdot 961 + 4 \cdot 29791 + 5 \cdot 923521 = 4739715$.

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

const ll M = 1234567891;
ll n;
string s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    ll h = 0, p = 1;
    for (ll i = 0; i < n; i++) {
        h = (h + (s[i] - 'a' + 1) * p) % M;
        p = p * 31 % M;
    }
    cout << h << '\n';
}

ChạyInput5
abcde

Output4739715

Chọn tham số

Lấy hai xâu khác nhau $s \ne t$ cùng độ dài $n$. Chúng trùng hash khi và chỉ khi $D(b)$ chia hết cho $M$, với $D(x) = (s_1 - t_1)\, x^{n-1} + (s_2 - t_2)\, x^{n-2} + \dots + (s_n - t_n)$. $D$ có bậc không quá $n - 1$ và không phải đa thức không. Khi $M$ là số nguyên tố, $D$ có nhiều nhất $n - 1$ nghiệm theo modulo $M$, nên nếu cơ số $b$ được bốc ngẫu nhiên đều trong $[0, M)$ sau khi hai xâu đã cố định, thì xác suất hai xâu trùng hash không quá

Với $M = 10^9 + 7$ và $n = 10^5$, cận này là $10^{-4}$; với $M = 2^{61} - 1$ nó là $4{,}3 \cdot 10^{-14}$. Hai điều kiện của chứng minh cũng là hai quy tắc chọn tham số: $M$ phải nguyên tố, và cơ số phải ngẫu nhiên, bốc lúc chạy chương trình (cơ số cố định thì ai biết nó dựng được hai xâu trùng hash, đúng việc người ta làm ở các kỳ thi cho phép hack).

Cận trên chỉ nói về một cặp. Nhiều thuật toán so mọi cặp cùng lúc: bỏ hash của $m$ xâu vào một tập, hoặc sắp xếp rồi tìm hai hash bằng nhau. Có $\approx m^2/2$ cặp, mỗi cặp trùng với xác suất cỡ $1/M$, nên trung bình có khoảng $m^2/(2M)$ cặp trùng nhầm; con số này vượt 1 là gần như chắc chắn có trùng. Hiện tượng này gọi là nghịch lý ngày sinh (birthday paradox). Với $M \approx 10^9$ và $m = 10^5$, xác suất trùng là $99{,}3\%$; với $M = 2^{61} - 1$ chỉ cỡ $2 \cdot 10^{-9}$. Quy tắc: so $q$ cặp định sẵn thì modulo $10^9$ cho xác suất sai khoảng $q/10^9$; so mọi cặp trong $m$ hash thì cần $M \gg m^2$, tức cỡ $10^{18}$: một modulo $2^{61} - 1$, hoặc hai modulo nguyên tố cỡ $10^9$ với hai cơ số độc lập.

Hash tràn số bị bẻ. Phép % chậm, nên nhiều người dùng unsigned long long và để phép tính tự tràn, tức tính theo modulo $2^{64}$. Nhưng $2^{64}$ không phải số nguyên tố, và có hẳn một cặp xâu trùng hash với mọi cơ số lẻ. Đặt $S_0 = $ a và $S_k = S_{k-1}\overline{S_{k-1}}$, với $\overline{X}$ là $X$ đổi a và b cho nhau: chuỗi Thue-Morse ab, abba, abbabaab, ...

Hình dưới tính hash thật theo modulo $2^{64}$ cho xâu Thue-Morse và xâu đảo của nó. Đổi cơ số lẻ để thử.

Từ $H(XY) = H(X)\, b^{|Y|} + H(Y)$ suy ra hiệu $D_k = H(S_k) - H(\overline{S_k})$ thỏa $D_k = D_{k-1}(b^{2^{k-1}} - 1)$, tức $D_k$ bằng tích $(b - 1)(b^2 - 1)(b^4 - 1) \cdots (b^{2^{k-1}} - 1)$, đổi dấu. Với $b$ lẻ, thừa số $i = 0$ chẵn, còn với $i \ge 1$ thừa số $b^{2^i} - 1$ chia hết cho $2^{i+2}$. Số thừa số 2 của $D_{10}$ ít nhất là $1 + (3 + 4 + \dots + 11) = 64$: hai xâu $S_{10}$ và $\overline{S_{10}}$, dài 1024, trùng hash modulo $2^{64}$ với mọi cơ số lẻ. Cơ số chẵn còn tệ hơn, vì $b^{64} \equiv 0$ nên chỉ 64 ký tự cuối còn ảnh hưởng.

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

ull calc(string s, ull b) {
    ull h = 0;
    for (char c : s) h = h * b + (c - 'a' + 1);
    return h;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string a, b;
    for (ll i = 0; i < 1024; i++) {
        bool bit = __builtin_popcountll(i) % 2;
        a += bit ? 'b' : 'a';
        b += bit ? 'a' : 'b';
    }
    cout << (a == b ? "giong" : "khac") << ' ' << a.size() << '\n';
    for (ull base : {31ULL, 131ULL, 911382323ULL, 1000000007ULL, 123456789012345ULL})
        cout << base << ' ' << (calc(a, base) == calc(b, base) ? "trung" : "khac") << '\n';
}

Outputkhac 1024
31 trung
131 trung
911382323 trung
1000000007 trung
123456789012345 trung

Bốc cơ số lẻ ngẫu nhiên không cứu được, vì lỗi nằm ở modulo chứ không ở cơ số; thêm một hash tràn số thứ hai cũng vô ích. Test này có từ một kỳ thi học sinh ở Saint Petersburg năm 2003; nhiều thế hệ thí sinh hash tràn số bị WA vì nó mà không hiểu lý do, cho tới khi Zlobober giải thích trên Codeforces.

Cài đặt với $M = 2^{61} - 1$. Đây là một số nguyên tố, và tích hai số dưới $2^{61}$ nhỏ hơn $2^{122}$, nên nhân bằng __int128. Vì $2^{61} \equiv 1 \pmod M$, tích $t = \mathrm{hi} \cdot 2^{61} + \mathrm{lo}$ cho $t \equiv \mathrm{hi} + \mathrm{lo}$, nhỏ hơn $2M$, trừ $M$ một lần là xong. Cơ số bốc ngẫu nhiên một lần khi chạy, dùng chung cho mọi xâu cần so với nhau. Khi trình biên dịch không có __int128, thay bằng hai modulo nguyên tố cỡ $10^9$ với hai cơ số ngẫu nhiên, ghép hai hash vào một số 64 bit để so như một.

Dùng modulo lớn có làm chậm không?

Ba cách chênh nhau chưa tới 1,3 lần, và modulo $2^{61} - 1$ không chậm hơn một modulo $10^9$. Quy tắc: không có lý do tiết kiệm modulo; luôn dùng $2^{61} - 1$ hay hai modulo.

Ví dụNhững Điểm Khớp

Đề. Cho văn bản $T$ ($|T| \le 10^6$) và mẫu $P$ ($|P| \le 10^4$), gồm chữ cái Latin và chữ số. In mọi chỉ số $i$ (đánh số từ 0) mà $T$ bắt đầu tại $i$ khớp $P$, kể cả các lần chồng lấn.

Lời giải. Thuật toán Rabin-Karp: hash của $P$ một lần, rồi so với hash của mọi cửa sổ dài $|P|$ của $T$, lấy ra trong $O(1)$ từ mảng hash tiền tố. Hai xâu phải dùng cùng cơ số $B$. Số cặp được so chỉ là $10^6$ cặp định sẵn (mỗi cửa sổ với $P$), nên với modulo $2^{61} - 1$ xác suất sai không đáng kể.

Bước 1: nhân theo modulo $2^{61} - 1$. Tích hai số dưới $2^{61}$ cần 122 bit, nên tính trong __int128. Vì $2^{61} \equiv 1$, phần bit cao (dịch phải 61) cộng thẳng vào phần bit thấp (61 bit cuối) là đã lấy dư gần xong; một lần trừ cuối cho kết quả nhỏ hơn modulo.

ull mul(ull a, ull b) {
    __int128 t = (__int128)a * b;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

Bước 2: hash tiền tố và hash một đoạn. f[i] là hash của $i$ ký tự đầu. Hash của đoạn $[l, r]$ là f[r] trừ f[l - 1] đã dịch $r - l + 1$ chỗ (nhân $B^{r-l+1}$); cộng MOD trước khi trừ để không âm. Mã ASCII của chữ và số đều $\ge 1$ nên dùng thẳng làm giá trị ký tự.

void build(string s, ull f[]) {
    for (ll i = 1; i <= (ll)s.size(); i++) f[i] = (mul(f[i - 1], B) + s[i - 1]) % MOD;
}

ull get(ull f[], ll l, ll r) {
    return (f[r] + MOD - mul(f[l - 1], pw[r - l + 1])) % MOD;
}

Bước 3: so mọi cửa sổ. Cửa sổ bắt đầu ở vị trí $i$ (đếm từ 1) của mảng hash là chỉ số $i - 1$ của đề.

for (ll i = 1; i + m - 1 <= n; i++)
    if (get(h, i, i + m - 1) == g[m]) cout << i - 1 << '\n';

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

const ull MOD = (1ULL << 61) - 1;
const ll N = 1e6 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500, h[N], g[N], pw[N];

ull mul(ull a, ull b) {
    __int128 t = (__int128)a * b;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

void build(string s, ull f[]) {
    for (ll i = 1; i <= (ll)s.size(); i++) f[i] = (mul(f[i - 1], B) + s[i - 1]) % MOD;
}

ull get(ull f[], ll l, ll r) {
    return (f[r] + MOD - mul(f[l - 1], pw[r - l + 1])) % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string t, p;
    cin >> t >> p;
    ll n = t.size(), m = p.size();
    pw[0] = 1;
    for (ll i = 1; i <= n; i++) pw[i] = mul(pw[i - 1], B);
    build(t, h);
    build(p, g);
    for (ll i = 1; i + m - 1 <= n; i++)
        if (get(h, i, i + m - 1) == g[m]) cout << i - 1 << '\n';
}

ChạyInputababaabababa
aba

Output0
2
5
7
9

Cả bài $O(|T| + |P|)$.

Hash và chặt nhị phân

Hash so hai đoạn trong $O(1)$, nên mọi tính chất kiểu “hai đoạn dài $L$ bằng nhau” kiểm được nhanh. Khi tính chất đó đơn điệu theo $L$, ta chặt nhị phân (bài 05) trên $L$.

Tiền tố chung dài nhất. Gọi $\mathrm{lcp}(i, j)$ là $L$ lớn nhất để $s[i..i+L-1] = s[j..j+L-1]$. Nếu $L$ ký tự đầu của hai hậu tố bằng nhau thì $L - 1$ ký tự đầu cũng bằng nhau, nên chặt nhị phân trên $L$ cho đáp án sau $O(\log n)$ lần so hash. So hai hậu tố theo thứ tự từ điển cũng xong ngay: tìm $\mathrm{lcp}$ rồi so ký tự kế tiếp. Với hàm get như trên:

ll lcp(ll i, ll j) {
    ll l = 0, r = n - max(i, j) + 1, res = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (get(h, i, i + mid - 1) == get(h, j, j + mid - 1)) l = (res = mid) + 1;
        else r = mid - 1;
    }
    return res;
}

Với $s$ = abracadabra: $\mathrm{lcp}(1, 8) = 4$, $\mathrm{lcp}(1, 4) = 1$, $\mathrm{lcp}(3, 5) = 0$.

Trong hình, mỗi bước so hash của hai đoạn dài $L$; ô xanh là đoạn bằng nhau, ô đỏ là khác.

Đối xứng. Một đoạn là palindrome nếu nó bằng chính nó viết ngược. Gọi $t$ là xâu đảo của $s$, $t_i = s_{n+1-i}$; đoạn $s[l..r]$ viết ngược chính là $t[n+1-r..n+1-l]$, nên dựng hash cho cả $s$ (mảng h) và $t$ (mảng g) rồi so get(h, l, r) với get(g, n + 1 - r, n + 1 - l). Với $s$ = dabacab, $t$ = bacabad: đoạn $[2, 4]$ là aba, ứng với $t[4..6]$ cũng là aba.

Trong hình, mỗi đường nối một ký tự của $s$ với đúng vị trí của nó trong $t$. Kéo $l$, $r$ để thử đoạn khác.

Xâu con đối xứng dài nhất thì cần cẩn thận. Tính chất “có xâu con đối xứng dài $L$” không đơn điệu trên mọi $L$: abcba có xâu đối xứng dài 5, 3, 1 nhưng không có dài 4 hay 2. Cái đúng là đơn điệu trong từng loại chẵn lẻ, vì bỏ ký tự đầu và cuối của một palindrome dài $L \ge 3$ được palindrome dài $L - 2$. Vậy chặt nhị phân riêng cho độ dài lẻ và độ dài chẵn, mỗi lần kiểm quét $O(n)$ cửa sổ, cả bài $O(n \log n)$.

Ví dụĐoạn Lặp Dài Nhất

Đề. Cho xâu $s$ gồm chữ thường, dài $n \le 2 \cdot 10^5$. In độ dài lớn nhất của một xâu con xuất hiện ở ít nhất hai vị trí bắt đầu khác nhau (được chồng lấn, như aba trong ababa); không có thì in 0.

Lời giải. Gọi $\mathrm{rep}(L)$ là “có một xâu con dài $L$ xuất hiện tại hai vị trí khác nhau”. Nếu $\mathrm{rep}(L)$ đúng thì $\mathrm{rep}(L - 1)$ cũng đúng: bỏ ký tự cuối của cả hai lần xuất hiện. Vậy chặt nhị phân $L$ trong $[1, n - 1]$, mỗi lần kiểm $\mathrm{rep}(L)$ bằng hash. Với ababa: $L = 4$ cho abab, baba, khác nhau; $L = 3$ có aba hai lần.

Bước 1: hash tiền tố. Như ví dụ trước, mul nhân theo modulo $2^{61} - 1$ và get(l, r) cho hash của đoạn $[l, r]$ trong $O(1)$. Mảng lũy thừa và mảng hash tính chung một vòng.

pw[0] = 1;
for (ll i = 1; i <= n; i++) {
    pw[i] = mul(pw[i - 1], B);
    h[i] = (mul(h[i - 1], B) + s[i - 1]) % MOD;
}

Bước 2: kiểm một độ dài. Lấy hash của mọi cửa sổ dài $L$, sắp xếp; có lặp khi hai hash bằng nhau đứng cạnh nhau. Đây là tình huống “so mọi cặp”: khoảng $n^2 / 2 = 2 \cdot 10^{10}$ cặp cửa sổ có thể trùng hash, nên một modulo $10^9$ sẽ gần như chắc chắn báo trùng nhầm; với $2^{61} - 1$, số cặp trùng nhầm kỳ vọng chỉ cỡ $10^{-8}$.

bool check(ll len) {
    vector<ull> v;
    for (ll i = 1; i + len - 1 <= n; i++) v.push_back(get(i, i + len - 1));
    sort(v.begin(), v.end());
    for (ll i = 1; i < (ll)v.size(); i++)
        if (v[i] == v[i - 1]) return 1;
    return 0;
}

Bước 3: chặt nhị phân độ dài. Tìm $L$ lớn nhất có check(L) đúng; không có thì giữ 0.

ll l = 1, r = n - 1, res = 0;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (check(mid)) l = (res = mid) + 1;
    else r = mid - 1;
}

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

const ull MOD = (1ULL << 61) - 1;
const ll N = 2e5 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500, h[N], pw[N];
ll n;
string s;

ull mul(ull a, ull b) {
    __int128 t = (__int128)a * b;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

ull get(ll l, ll r) {
    return (h[r] + MOD - mul(h[l - 1], pw[r - l + 1])) % MOD;
}

bool check(ll len) {
    vector<ull> v;
    for (ll i = 1; i + len - 1 <= n; i++) v.push_back(get(i, i + len - 1));
    sort(v.begin(), v.end());
    for (ll i = 1; i < (ll)v.size(); i++)
        if (v[i] == v[i - 1]) return 1;
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    pw[0] = 1;
    for (ll i = 1; i <= n; i++) {
        pw[i] = mul(pw[i - 1], B);
        h[i] = (mul(h[i - 1], B) + s[i - 1]) % MOD;
    }
    ll l = 1, r = n - 1, res = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) l = (res = mid) + 1;
        else r = mid - 1;
    }
    cout << res << '\n';
}

ChạyInput5
ababa

Output3

Khoảng $\log_2 n \approx 18$ lần kiểm, mỗi lần sắp $n$ hash: $O(n \log n \cdot \log n)$.

Hash tập và đa tập

Hash đa thức nhạy với thứ tự: ab và ba có hash khác nhau. Có những bài chỉ quan tâm phần tử nào có mặt và bao nhiêu lần. Ví dụ, cho dãy $a_1, \dots, a_n$ và các truy vấn $(l, r)$: đoạn $a[l..r]$ có phải một hoán vị của $1, 2, \dots, r - l + 1$ không? Sắp xếp từng đoạn tốn $O(n \log n)$ mỗi truy vấn.

Cách làm là bỏ hẳn đa thức. Gán cho mỗi giá trị $v$ một trọng số ngẫu nhiên $w(v)$ cỡ 64 bit, và lấy hash của đa tập là tổng các trọng số của các phần tử, theo modulo $2^{64}$. Phép cộng giao hoán nên thứ tự biến mất, còn số lần xuất hiện vẫn được giữ vì giá trị xuất hiện $c$ lần đóng góp $c \cdot w(v)$. Tổng tiền tố của các trọng số cho hash của mọi đoạn trong $O(1)$; đoạn là hoán vị của $1..k$ khi hash của nó bằng $w(1) + \dots + w(k)$. Trọng số tính từ chính giá trị $v$ bằng hàm trộn splitmix64 cộng một hạt giống lấy từ đồng hồ, khỏi cần bảng.

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

const ll N = 2e5 + 5;
const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
ll n, q;
ull pre[N], full[N];

ull w(ull v) {
    ull x = v + SEED + 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        pre[i] = pre[i - 1] + w(a);
        full[i] = full[i - 1] + w(i);
    }
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << (pre[r] - pre[l - 1] == full[r - l + 1] ? "YES" : "NO") << '\n';
    }
}

ChạyInput6 6
3 1 2 5 4 2
1 3
2 4
3 6
1 5
4 5
6 6

OutputYES
NO
NO
YES
NO
NO

Chương trình này cố ý để unsigned long long tràn, khác hẳn hash tràn số ở mục trước, và nó an toàn nhờ các trọng số coi như ngẫu nhiên, độc lập. Hai đa tập khác nhau ở ít nhất một giá trị $u$ với số lần chênh $d \ne 0$, $|d| \le n$; hiệu hai hash có dạng $d \cdot w(u) + X$, và với $2^j$ là lũy thừa 2 lớn nhất chia hết $d$, phương trình $d \cdot w(u) \equiv -X$ có không quá $2^j$ nghiệm trong $2^{64}$ giá trị. Với $n < 2^{18}$ xác suất sai nhỏ hơn $2^{-47}$ mỗi truy vấn. Với tập (bỏ qua số lần xuất hiện) ta XOR thay vì cộng, và chỉ XOR một giá trị vào hash ở lần xuất hiện đầu tiên của nó.

Ví dụTập Tiền Tố

Đề. Hai dãy $A$, $B$ cùng $N \le 2 \cdot 10^5$ phần tử, giá trị tới $10^9$. Mỗi trong $Q \le 2 \cdot 10^5$ truy vấn $(x, y)$ hỏi tập các giá trị trong $A_1..A_x$ có bằng tập các giá trị trong $B_1..B_y$ không.

Lời giải. Gán mỗi giá trị một trọng số ngẫu nhiên 64 bit; chữ ký của một tập là XOR trọng số của các giá trị phân biệt có mặt. Hai tập bằng nhau thì chữ ký bằng nhau. Hai tập khác nhau thì XOR hai chữ ký bằng XOR trọng số trên hiệu đối xứng khác rỗng, bằng 0 với xác suất $2^{-64}$. Vậy mỗi truy vấn chỉ là so hai số đã tính sẵn. Với ví dụ, $\{5, 1\}$ và $\{1, 5\}$ bằng nhau nên truy vấn 2 là Yes.

Bước 1: trọng số của một giá trị. Hàm w trộn giá trị (cộng một hạt giống lấy từ đồng hồ) qua vài phép nhân và dịch bit, cho một số 64 bit trông như ngẫu nhiên; cùng giá trị luôn cho cùng trọng số. Hạt giống đổi mỗi lần chạy để không ai dựng được test làm trùng.

ull w(ull v) {
    ull x = v + SEED + 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

Bước 2: chữ ký tiền tố của tập. Quét dãy từ trái sang, chữ ký chỉ đổi ở vị trí giá trị xuất hiện lần đầu. Lần lặp sau phải giữ nguyên, nếu không XOR hai lần làm giá trị biến mất khỏi chữ ký. seen.insert(x).second cho biết $x$ vừa được thêm lần đầu.

void build(ll a[], ull p[]) {
    set<ll> seen;
    for (ll i = 1; i <= n; i++) {
        p[i] = p[i - 1];
        if (seen.insert(a[i]).second) p[i] ^= w(a[i]);
    }
}

Bước 3: trả lời. So pa[x] với pb[y].

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

const ll N = 2e5 + 5;
const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
ll n, q, a[N], b[N];
ull pa[N], pb[N];

ull w(ull v) {
    ull x = v + SEED + 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

void build(ll a[], ull p[]) {
    set<ll> seen;
    for (ll i = 1; i <= n; i++) {
        p[i] = p[i - 1];
        if (seen.insert(a[i]).second) p[i] ^= w(a[i]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) cin >> b[i];
    build(a, pa);
    build(b, pb);
    cin >> q;
    while (q--) {
        ll x, y;
        cin >> x >> y;
        cout << (pa[x] == pb[y] ? "Yes" : "No") << '\n';
    }
}

ChạyInput6
5 1 5 2 3 2
1 5 1 3 2 4
6
1 1
2 2
3 3
4 4
5 5
6 6

OutputNo
Yes
Yes
No
Yes
No

Dựng $O(N \log N)$ vì set, mỗi truy vấn $O(1)$.

Dãy số, bảng, cập nhật

Dãy số. Hash đa thức dùng được cho dãy số nguyên: coi mỗi phần tử là một ký tự có giá trị trong $[1, M)$, cộng thêm một hằng số nếu có số âm hoặc số 0. Nhiều bài hỏi khớp mẫu sai khác một hằng số: đoạn $a[l..l+m-1]$ khớp $b$ nếu có $x$ để $a_{l+i} = b_i + x$ với mọi $i$. Cộng cùng một số vào mọi phần tử không đổi hiệu hai phần tử liền kề, nên điều kiện tương đương là hai dãy hiệu bằng nhau; ta hash hai dãy hiệu rồi so khớp như xâu.

Bảng hai chiều. Để tìm một mẫu hình chữ nhật trong bảng ký tự, hash từng cửa sổ ngang của mỗi hàng bằng cơ số $b_1$, rồi coi mỗi hash hàng là một ký tự và hash theo chiều dọc bằng cơ số $b_2$ khác.

Dữ liệu bị sửa. Với mảng tiền tố, đổi một ký tự làm hỏng mọi $h_i$ phía sau. Khi cập nhật xen kẽ truy vấn, lưu hash trong cây phân đoạn (bài 17): mỗi nút giữ hash và độ dài đoạn của nó, ghép hai nút con theo $H(L) \cdot b^{|R|} + H(R)$. Kiểm tra palindrome có cập nhật cần hai cây, một cho $s$ và một cho xâu đảo.

Ví dụMẫu Cao Độ Dịch Chuyển

Đề. Cho dãy $a$ gồm $n$ số và dãy $b$ gồm $m$ số ($n, m \le 2 \cdot 10^5$, giá trị tới $10^9$). Đếm số vị trí $l$ mà có $x$ (tùy ý, được khác nhau giữa các vị trí) để $a_{l+i} = b_i + x$ với mọi $i$.

Lời giải. Đổi hai dãy thành dãy hiệu: $da_i = a_{i+1} - a_i$ dài $n - 1$, $db_i = b_{i+1} - b_i$ dài $m - 1$. Một đoạn của $a$ khớp $b$ (sau khi cộng cùng một $x$) khi và chỉ khi đoạn hiệu tương ứng dài $m - 1$ bằng $db$: phép cộng $x$ không đổi hiệu. Bài thành so khớp mẫu trên hai dãy số, giải bằng hash như ví dụ đầu. Với ví dụ, $db = (2, 1)$ khớp ở đầu và ở vị trí 3 của dãy hiệu $(2, 1, -6, 2, 1, 5, 2)$.

Bước 1: hai trường hợp biên. $m = 1$ thì dãy hiệu rỗng và mọi vị trí đều khớp, đáp án là $n$. Khi $m > n$ thì vòng so ở bước 3 không chạy lần nào, đáp án tự là 0.

if (m == 1) {
    cout << n << '\n';
    return 0;
}

Bước 2: hash của hai dãy hiệu. Hiệu nằm trong $[-10^9, 10^9]$; cộng $10^9 + 1$ cho thành số dương rồi dùng làm giá trị “ký tự”.

for (ll i = 1; i < n; i++) {
    pw[i] = mul(pw[i - 1], B);
    h[i] = (mul(h[i - 1], B) + (ull)(a[i + 1] - a[i] + 1000000001)) % MOD;
}
for (ll i = 1; i < m; i++) g[i] = (mul(g[i - 1], B) + (ull)(b[i + 1] - b[i] + 1000000001)) % MOD;

Bước 3: so mọi cửa sổ dài $m - 1$.

ll len = m - 1, ans = 0;
for (ll i = 1; i + len - 1 <= n - 1; i++)
    if ((h[i + len - 1] + MOD - mul(h[i - 1], pw[len])) % MOD == g[len]) ans++;

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

const ull MOD = (1ULL << 61) - 1;
const ll N = 2e5 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500, h[N], g[N], pw[N];
ll n, m, a[N], b[N];

ull mul(ull x, ull y) {
    __int128 t = (__int128)x * y;
    ull r = (ull)(t & MOD) + (ull)(t >> 61);
    return r >= MOD ? r - MOD : r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= m; i++) cin >> b[i];
    if (m == 1) {
        cout << n << '\n';
        return 0;
    }
    pw[0] = 1;
    for (ll i = 1; i < n; i++) {
        pw[i] = mul(pw[i - 1], B);
        h[i] = (mul(h[i - 1], B) + (ull)(a[i + 1] - a[i] + 1000000001)) % MOD;
    }
    for (ll i = 1; i < m; i++) g[i] = (mul(g[i - 1], B) + (ull)(b[i + 1] - b[i] + 1000000001)) % MOD;
    ll len = m - 1, ans = 0;
    for (ll i = 1; i + len - 1 <= n - 1; i++)
        if ((h[i + len - 1] + MOD - mul(h[i - 1], pw[len])) % MOD == g[len]) ans++;
    cout << ans << '\n';
}

ChạyInput8 3
5 7 8 2 4 5 10 12
1 3 4

Output2

Cả bài $O(n + m)$.