Chương 34 - Rolling Hash

Rolling Hash = hash chuỗi mà ta có thể “trượt window” với O(1) cập nhật. Pattern này biến O(n · m) thành O(n + m) cho bài substring matching, duplicate detection, …

Mục tiêu chương

Sau chương này, bạn sẽ:

• Rolling hash trượt 1 ký tự trong O(1).
• Collision: LC OK với 1 hash + MOD lớn (Mersenne (1<<61)-1); production cần double hash.
• Pattern: substring matching, distinct substring, palindrome check.
• So với KMP/Z: rolling hash dễ code, KMP/Z deterministic (không collision).

Khi nào dùng pattern này?

• Tìm substring (alternative cho KMP).
• Detect duplicate substring có độ dài cố định.
• Bài longest/distinct substring với constraint.

Pattern (Rabin-Karp):

hash(s[l..r]) = (s[l]·base^(r-l) + s[l+1]·base^(r-l-1) + ... + s[r]) mod M

Khi trượt: hash_new = (hash_old · base + s[r+1] - s[l] · base^(r-l+1)) mod M

Bẫy va chạm (collision). Modulo nguyên tố 10^9 + 7 thường an toàn cho bài LC; nếu có adversary cố tình tấn công, dùng 2 hash khác nhau (double hashing).

Template code

def rolling_hash(s: str, length: int) -> set[int]:
    BASE = 26
    MOD = (1 << 61) - 1
    n = len(s)
    base_pow = pow(BASE, length, MOD)
    h = 0
    seen = set()
    for i in range(n):
        h = (h * BASE + ord(s[i])) % MOD
        if i >= length:
            h = (h - ord(s[i - length]) * base_pow) % MOD
        if i >= length - 1:
            seen.add(h)
    return seen

Bài tự luyện cuối chương

• LC 28 - Find the Index of the First Occurrence
• LC 686 - Repeated String Match
• LC 1147 - Longest Chunked Palindrome Decomposition

---

34.1 Repeated DNA Sequences (LC 187)

Đề bài

Cho chuỗi DNA s (chứa A, C, G, T). Trả về substring độ dài 10 xuất hiện ≥ 2 lần.

Ví dụ

Input:  s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"   (chuỗi chỉ chứa A/C/G/T)
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
        (mọi substring độ dài 10 xuất hiện ≥ 2 lần; thứ tự không quan trọng)

Ràng buộc

• 0 <= len(s) <= 10^5
• s chỉ chứa A, C, G, T

Clarifying questions

• String < 10 ký tự? → Trả [].
• Substring trùng > 2 lần? → Vẫn chỉ thêm 1 lần vào output.

Hướng tiếp cận

Brute force: set substring 10-char. O(n · 10) time, O(n · 10) space.

Rolling hash: O(n) time, O(n) space (memory smaller because hash là int).

Code Python 3

from typing import List

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seen: dict[str, int] = {}
        result: list[str] = []
        for i in range(len(s) - 9):
            sub = s[i:i + 10]
            seen[sub] = seen.get(sub, 0) + 1
            if seen[sub] == 2:
                result.append(sub)
        return result

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n).

Bình luận

• Bài này simple → set thuần đủ.

Bài tự luyện liên quan

• LC 1044 - Longest Duplicate Substring (bài 34.2)
• LC 1147 - Longest Chunked Palindrome Decomposition

---

34.2 Longest Duplicate Substring (LC 1044)

Đề bài

Cho s. Tìm substring dài nhất xuất hiện ít nhất 2 lần (có thể overlap). Nếu nhiều, trả bất kỳ.

Ví dụ

Input:  s = "banana"
Output: "ana"   (substring lặp lại dài nhất; nếu nhiều, trả về bất kỳ)

Ràng buộc

• 2 <= len(s) <= 3·10^4
• s chỉ chứa chữ thường

Clarifying questions

• Tie nhiều substring cùng độ dài? → Trả bất kỳ.

Hướng tiếp cận

Binary search trên length + rolling hash check.

• Tìm độ dài lớn nhất L mà có substring length-L xuất hiện ≥ 2 lần.
• Predicate đơn điệu: nếu length L có, mọi length < L cũng có.

check(L): rolling hash + set; nếu collision → có duplicate.

Code Python 3

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        BASE = 26
        MOD = (1 << 61) - 1
        n = len(s)
        nums = [ord(c) - ord('a') for c in s]

        def search(L: int) -> int:
            base_pow = pow(BASE, L, MOD)
            h = 0
            for i in range(L):
                h = (h * BASE + nums[i]) % MOD
            seen = {h: 0}
            for i in range(1, n - L + 1):
                h = (h * BASE - nums[i - 1] * base_pow + nums[i + L - 1]) % MOD
                if h in seen:
                    return i
                seen[h] = i
            return -1

        lo, hi = 1, n - 1
        start = 0
        best_len = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            idx = search(mid)
            if idx != -1:
                if mid > best_len:
                    best_len = mid
                    start = idx
                lo = mid + 1
            else:
                hi = mid - 1
        return s[start:start + best_len]

Phân tích độ phức tạp

• Thời gian: O(n log n). Bộ nhớ: O(n).

Bình luận

• Bài Hard. Rolling hash + binary search là cú combo sát thủ.
• Collision risk: với MOD = (1<<61)-1 (Mersenne prime), an toàn cho LC.

Bài tự luyện liên quan

• LC 1316 - Distinct Echo Substrings (bài 34.3)
• LC 187 - Repeated DNA Sequences (bài 34.1)

---

34.3 Distinct Echo Substrings (LC 1316)

Đề bài

Đếm số substring phân biệt có dạng a + a (concat của chuỗi với chính nó).

Ví dụ

Input:  text = "abcabcabc"
Output: 3
(số echo substring khác nhau; echo = substring dạng a+a;
 ở đây có "abcabc", "bcabca", "cabcab")

Ràng buộc

• 1 <= len(text) <= 2000
• text chỉ chứa chữ thường

Clarifying questions

• s rỗng? → Trả 0.
• Echo bao gồm overlap? → Theo định nghĩa: a + a không overlap.

Hướng tiếp cận

Với mỗi L (độ dài a), check mọi vị trí có s[i..i+L-1] == s[i+L..i+2L-1]. Rolling hash giúp so sánh O(1). Collect các hash đã thấy.

Code Python 3

class Solution:
    def distinctEchoSubstrings(self, s: str) -> int:
        n = len(s)
        BASE = 26
        MOD = (1 << 61) - 1
        nums = [ord(c) - ord('a') for c in s]

        # Precompute prefix hash + power.
        h = [0] * (n + 1)
        p = [1] * (n + 1)
        for i in range(n):
            h[i + 1] = (h[i] * BASE + nums[i]) % MOD
            p[i + 1] = (p[i] * BASE) % MOD

        def get_hash(l: int, r: int) -> int:
            return (h[r + 1] - h[l] * p[r - l + 1]) % MOD

        seen: set[int] = set()
        for L in range(1, n // 2 + 1):
            for i in range(n - 2 * L + 1):
                h1 = get_hash(i, i + L - 1)
                h2 = get_hash(i + L, i + 2 * L - 1)
                if h1 == h2:
                    seen.add(h1)
        return len(seen)

Phân tích độ phức tạp

• Thời gian: O(n²). Bộ nhớ: O(n²) worst.

Bình luận

• Bẫy: O(n²) loop với slice → có thể bị TLE; nên dùng prefix hash để check substring trong O(1).
• Follow-up: LC 1044 (Longest Duplicate) cùng pattern hash.

Bài tự luyện liên quan

• LC 1044 - Longest Duplicate Substring (bài 34.2)
• LC 187 - Repeated DNA Sequences

---

34.4 Shortest Palindrome (LC 214) - Rolling Hash version

Đề bài

Cho s. Thêm ký tự vào đầu sao cho s thành palindrome, đầu càng ít càng tốt.

Ví dụ

Input:  s = "aacecaaa"
Output: "aaacecaaa"   (thêm ký tự ÍT NHẤT vào ĐẦU s để thành palindrome)

Ràng buộc

• 0 <= len(s) <= 5·10^4
• s chỉ chứa chữ thường

Clarifying questions

• s đã là palindrome? → Trả s (không cần thêm).

Hướng tiếp cận

Tìm prefix dài nhất của s là palindrome. Phần còn lại reverse và thêm vào đầu.

Rolling hash approach: compute hash của s và reverse(s). Tìm L lớn nhất mà hash(s[:L]) == hash(rev_s[n-L:]) (= s[:L] palindrome).

Code Python 3

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1: return s
        BASE = 131
        MOD = 10**9 + 7
        h1 = h2 = 0
        power = 1
        best = 0
        for i, ch in enumerate(s):
            h1 = (h1 * BASE + ord(ch)) % MOD
            h2 = (h2 + ord(ch) * power) % MOD
            power = power * BASE % MOD
            if h1 == h2:
                best = i + 1
        return s[best:][::-1] + s

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(1).

Bình luận

• h1 = hash đọc xuôi prefix [0..i].
• h2 = hash đọc ngược (vẫn prefix [0..i] nhưng order ngược).
• Khi bằng nhau → prefix là palindrome.

Bài tự luyện liên quan

• LC 214 - KMP version (Chương 35).

---

34.5 Strings Differ by One Character (LC 1638)

Đề bài

Cho dict các chuỗi cùng độ dài. Trả về True nếu tồn tại 2 chuỗi chỉ khác đúng 1 ký tự.

Ví dụ

Input:  dict = ["abcd", "acbd", "aacd"]
Output: True   (tồn tại 2 chuỗi cùng độ dài khác đúng 1 vị trí; ví dụ "abcd" vs "aacd")

Ràng buộc

• 2 <= len(dict) <= 100
• 1 <= len(dict[i]) <= 20

Clarifying questions

• dict có 2 chuỗi giống hệt? → Differ 0 chứ không phải 1 → False.
• Empty dict? → False.

Hướng tiếp cận

Cho mỗi chuỗi và mỗi vị trí i, “mask” ký tự thứ i → hash phần còn lại. Nếu trùng → có cặp khác 1 vị trí.

Code Python 3

from typing import List

class Solution:
    def differByOne(self, dict: List[str]) -> bool:
        n_words = len(dict)
        L = len(dict[0])
        seen: set[tuple[int, str, int]] = set()
        for w in dict:
            for i in range(L):
                key = (i, w[:i] + w[i+1:])
                if key in seen:
                    return True
                seen.add(key)
        return False

Phân tích độ phức tạp

• Thời gian: O(N · L²) worst (slice cost).
• Bộ nhớ: O(N · L).

Bình luận

• Đơn giản hơn rolling hash - Python string slice là O(L) nhưng OK cho LC.
• Rolling hash version đạt O(L · N) total tránh collision adversarial.

Bài tự luyện liên quan

• LC 1638 - Strings Differ by One Character (bài này)
• LC 686 - Repeated String Match

---

34.6 Sum of Scores of Built Strings (LC 2223)

Đề bài

Build s bằng cách prepend từng ký tự. Tại bước i, “score” = độ dài prefix dài nhất của s_i đồng thời là suffix của s_i. Tổng tất cả scores.

Ví dụ

Input:  s = "babab"
Output: 9   (score[i] = LCP(s, s[i:]); tổng score qua mọi i)

Ràng buộc

• 1 <= len(s) <= 10^5
• s chỉ chứa chữ thường

Clarifying questions

• Score của s_1 (1 ký tự)? → = 1.

Hướng tiếp cận

Z function ở Chương 36 là pattern chính. Rolling hash cũng giải được: với mỗi i tìm prefix-suffix length bằng binary search trên hash.

Code Python 3 (Z function - preview)

class Solution:
    def sumScores(self, s: str) -> int:
        # Z function - chi tiết ở Chương 36.
        n = len(s)
        z = [0] * n
        z[0] = n
        l = r = 0
        for i in range(1, n):
            if i < r:
                z[i] = min(r - i, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] > r:
                l, r = i, i + z[i]
        return sum(z)

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n).

Bình luận

• Bẫy: dùng định nghĩa s_i = s[n-i:] (build từ phải).
• Follow-up: Z function (Chương 36) giải cleaner.

Bài tự luyện liên quan

• LC 1392 - Longest Happy Prefix.

Tóm tắt chương & Quyết định

Rolling hash correctness - 2 cấp độ

Mục tiêu	Đủ
LC accepted	1 hash với prime modulus lớn (10⁹+7 hoặc (1<<61) - 1)
Production / robust	Double hash (2 cặp (base, mod)) hoặc kiểm chứng lại substring khi va chạm
Tuyệt đối không sai	Lưu substring thay hash → tốn bộ nhớ

Prefix-hash convention [l, r)

hash[i] = (hash[i-1] * base + ord(s[i-1])) mod M
substring s[l:r] hash = (hash[r] - hash[l] * pow_base[r - l]) mod M

Lưu ý Python: (a - b) % M luôn đúng (negative-safe). Java/C++ cần ((... % M) + M) % M.

Distinct Echo Substrings (LC 1316) - collision

• Đề bài chấp nhận với 1 hash trên LC.
• Production: nếu va chạm, kiểm chứng lại bằng so sánh substring trực tiếp (slice).

Rolling hash vs KMP/Z

	Rolling hash	KMP / Z
Tìm pattern P trong text T	O(|T|) avg, có thể va chạm	O(|T| + |P|) đảm bảo
Đa truy vấn (search nhiều pattern)	Cần index hash của T	Cần build per-pattern
Substring so sánh tổng quát	✅ Hash any range	KMP/Z không hỗ trợ trực tiếp
Risk va chạm	Có	Không

---