Hash xâu

Mức độ: Nâng cao

So sánh hai xâu dài L mất L bước. Một bài có 10⁵ câu hỏi “đoạn từ i đến j có giống đoạn từ k đến l không?” thì có thể mất tới 10¹⁰ bước. Hash xâu biến mỗi đoạn thành một số, rồi so sánh hai số thay vì so sánh từng ký tự. Nhờ tổng tiền tố, hash của mọi đoạn tính được trong một phép tính.

Hash đa thức

Đổi mỗi ký tự thành một số (ví dụ a → 1, b → 2, …). Hash của xâu c₁c₂…c_L là giá trị của một đa thức tại cơ số B, lấy dư cho một số nguyên tố lớn M:

hash = (c₁ × B^{L - 1} + c₂ × B^{L - 2} + … + c_L) mod M

Giống như đọc xâu như một số viết trong hệ cơ số B. Hai xâu giống nhau luôn có hash bằng nhau. Hai xâu khác nhau rất hiếm khi có hash bằng nhau (gọi là trùng hash), với M khoảng 10⁹ xác suất cỡ 1 / M cho mỗi lần so sánh.

Hash tiền tố và hash của một đoạn

Tính H[i] là hash của i ký tự đầu: H[0] = 0, H[i] = (H[i - 1] × B + c_i) mod M. Khi đó hash của đoạn từ vị trí l + 1 đến r (đánh số từ 1) là:

hash(l + 1, r) = (H[r] - H[l] × B^{r - l}) mod M

vì H[r] chứa cả phần đầu H[l] đã bị “đẩy lên” r - l bậc. Tính sẵn lũy thừa P[k] = B^k mod M.

Xâu abab với B = 10 (không lấy dư cho dễ thấy, a = 1, b = 2): H = 0, 1, 12, 121, 1212. Đoạn từ 3 đến 4 là H[4] - H[2] × 10² = 1212 - 1200 = 12, đúng bằng hash của ab (đoạn từ 1 đến 2 cũng là H[2] = 12).

Python

import sys
du_lieu = sys.stdin.read().split()
s, q = du_lieu[0], int(du_lieu[1])
n = len(s)
B, M = 131, (1 << 61) - 1                 # M nguyên tố rất lớn, Python tính số lớn được
H = [0] * (n + 1)
P = [1] * (n + 1)
for i, c in enumerate(s):
    H[i + 1] = (H[i] * B + ord(c)) % M
    P[i + 1] = P[i] * B % M

def hash_doan(l, r):                      # đoạn s[l:r], đánh số từ 0, không gồm r
    return (H[r] - H[l] * P[r - l]) % M

ket_qua = []
for t in range(q):
    a, b, c, d = (int(x) for x in du_lieu[2 + 4 * t:6 + 4 * t])   # hai đoạn [a, b] và [c, d], đánh số từ 1
    giong = b - a == d - c and hash_doan(a - 1, b) == hash_doan(c - 1, d)
    ket_qua.append("YES" if giong else "NO")
print("\n".join(ket_qua))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef unsigned long long ull;
const ull M = (1ULL << 61) - 1, B = 131;

ull nhan(ull a, ull b) {                  // (a * b) mod M không tràn số
    return (unsigned __int128)a * b % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int q;
    cin >> s >> q;
    int n = s.size();
    vector<ull> H(n + 1, 0), P(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (nhan(H[i], B) + s[i]) % M;
        P[i + 1] = nhan(P[i], B);
    }
    auto hashDoan = [&](int l, int r) {   // đoạn [l, r), đánh số từ 0
        return (H[r] + M - nhan(H[l], P[r - l])) % M;
    };
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        bool giong = b - a == d - c && hashDoan(a - 1, b) == hashDoan(c - 1, d);
        cout << (giong ? "YES" : "NO") << "\n";
    }
    return 0;
}

Chọn cơ số và modulo

• Cơ số B lớn hơn số loại ký tự (với chữ cái và chữ số, 131 là đủ), modulo M là số nguyên tố lớn.
• Với M = 10⁹ + 7, mỗi lần so sánh có khả năng trùng khoảng 10^-9; nhưng nếu so sánh rất nhiều cặp (ví dụ 10¹⁰ cặp xâu con) thì gần như chắc chắn có trùng. Khi đó dùng M = 2⁶¹ - 1 (như chương trình trên) hoặc hai modulo khác nhau cùng lúc.
• Hash chỉ cho biết “gần như chắc chắn bằng nhau”. Hash khác nhau thì hai xâu chắc chắn khác nhau.

Luyện tập

Gồm 14 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. So sánh đoạn và tìm mẫu

Bài 1. Hai đoạn có giống nhau không

Dòng đầu là xâu s (chữ cái thường, 1 ≤ |s| ≤ 2 × 10⁵) và số q (1 ≤ q ≤ 2 × 10⁵), q dòng sau mỗi dòng có a, b, c, d. Với mỗi câu hỏi, in ra YES nếu đoạn s_a…s_b giống hệt đoạn s_c…s_d (đánh số từ 1), ngược lại NO.

Ví dụ:

Nhập	In ra
abacaba 3 1 3 5 7 1 2 3 4 2 2 6 6	YES NO YES

Kiểm tra: nhập

bumbiibumbii 4
1 6 7 12
1 3 7 9
4 5 10 11
2 3 5 6

Xem đáp số

YES
YES
YES
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm số lần xuất hiện của mẫu

Dòng đầu là xâu t, dòng thứ hai là mẫu p (chữ cái thường, 1 ≤ |p| ≤ |t| ≤ 10⁶). In ra số vị trí trong t mà p xuất hiện bắt đầu từ đó (các lần xuất hiện có thể chồng lên nhau).

Ví dụ:

Nhập	In ra
abababa aba	3

Kiểm tra: nhập

bumbiibumbiibumbii
bii

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Đoạn đối xứng

Dòng đầu là xâu s (chữ cái thường, 1 ≤ |s| ≤ 2 × 10⁵) và số q (1 ≤ q ≤ 2 × 10⁵), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra YES nếu đoạn s_l…s_r là xâu đối xứng, ngược lại NO.

Ví dụ:

Nhập	In ra
abacabad 3 1 7 2 4 6 8	YES NO NO

Kiểm tra: nhập

racecarxabba 4
1 7
2 6
9 12
7 9

Xem đáp số

YES
YES
YES
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Thứ tự từ điển của hai đoạn

Dòng đầu là xâu s (chữ cái thường, 1 ≤ |s| ≤ 2 × 10⁵) và số q (1 ≤ q ≤ 2 × 10⁵), q dòng sau mỗi dòng có a, b, c, d. Với mỗi câu hỏi, so sánh đoạn X = s_a…s_b với đoạn Y = s_c…s_d theo thứ tự từ điển, in <, = hoặc >.

Ví dụ:

Nhập	In ra
abacabad 3 1 3 5 7 1 2 5 8 4 4 2 2	= < >

Kiểm tra: nhập

bumbiibumbii 4
1 6 7 12
1 4 7 9
5 6 4 5
2 2 1 3

Xem đáp số

=
>
>
>

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Nhiều mẫu cùng độ dài

Dòng đầu là xâu t (1 ≤ |t| ≤ 2 × 10⁵), dòng thứ hai có k và L (1 ≤ k ≤ 10⁵, 1 ≤ L ≤ |t|), k dòng sau mỗi dòng là một mẫu dài đúng L (chữ cái thường, k × L ≤ 10⁶). Với mỗi mẫu, in ra số lần nó xuất hiện trong t.

Ví dụ:

Nhập	In ra
abababa 3 2 ab ba aa	3 3 0

Kiểm tra: nhập

bumbiibumbii
4 3
bum
mbi
bii
xyz

Xem đáp số

2
2
2
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Cấu trúc của một xâu

Bài 6. Chu kỳ nhỏ nhất

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). In ra độ dài k nhỏ nhất sao cho s là một xâu độ dài k viết lặp lại nhiều lần (k phải là ước của |s|).

Ví dụ: nhập abcabcabc thì in ra 3.

Kiểm tra: nhập bumbiibumbiibumbiibumbii.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Tiền tố cũng là hậu tố

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). In ra, theo thứ tự tăng dần, mọi độ dài k (1 ≤ k nhỏ hơn |s|) mà k ký tự đầu của s giống hệt k ký tự cuối. Nếu không có, in ra -1.

Ví dụ: nhập abacaba thì in ra 1 3.

Kiểm tra: nhập aabaaabaabaa.

Xem đáp số

1 2 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Xoay vòng

Nhập hai xâu s và t cùng độ dài (chữ cái thường, 1 ≤ độ dài ≤ 10⁶) trên hai dòng. Xoay s nghĩa là chuyển một số ký tự đầu xuống cuối. In ra số lần xoay ít nhất (từ 0 đến |s| - 1 ký tự) để s thành t, hoặc -1 nếu không thể.

Ví dụ:

Nhập	In ra
abcde cdeab	2

Kiểm tra: nhập

bumbii
iibumb

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đếm xâu con

Bài 9. Số đoạn khác nhau có độ dài k

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶) và số k (1 ≤ k ≤ |s|) trên hai dòng. In ra số xâu khác nhau trong các đoạn dài đúng k của s.

Ví dụ:

Nhập	In ra
abababa 3	2

Kiểm tra: nhập

bumbiibumbiibumbii
4

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đếm mọi xâu con khác nhau

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 2000). In ra số xâu con khác rỗng khác nhau của s (xâu con là đoạn liên tiếp).

Ví dụ: nhập abab thì in ra 7.

Kiểm tra: nhập bumbiiacademy.

Xem đáp số

87

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Hash và tìm kiếm nhị phân

Bài 11. Đoạn chung dài nhất của hai xâu

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 10⁵). In ra độ dài đoạn liên tiếp dài nhất có mặt trong cả hai xâu.

Ví dụ:

Nhập	In ra
abcdxyz xyzabcd	4

Kiểm tra: nhập

bumbiiacademy
academicbumbii

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đoạn lặp lại dài nhất

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁵). In ra độ dài đoạn dài nhất xuất hiện ít nhất hai lần trong s (hai lần xuất hiện được chồng lên nhau), hoặc 0 nếu không có.

Ví dụ: nhập banana thì in ra 3.

Kiểm tra: nhập bumbiiacademybumbii.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Tìm mẫu sai tối đa một ký tự

Dòng đầu là xâu t, dòng thứ hai là mẫu p (chữ cái thường, 1 ≤ |p| ≤ |t| ≤ 2 × 10⁵). In ra số vị trí i trong t mà đoạn dài |p| bắt đầu ở i khác p tối đa một ký tự.

Ví dụ:

Nhập	In ra
abcabcabd abc	3

Kiểm tra: nhập

bumbiibumbiibumbii
bumbie

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đoạn đối xứng dài nhất

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 2 × 10⁵). In ra độ dài đoạn liên tiếp dài nhất của s là xâu đối xứng.

Ví dụ: nhập babad thì in ra 3.

Kiểm tra: nhập forgeeksskeegforabacabaxyz.

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.