Giao diện
Xử lý chuỗi nâng cao
🎯 Mục tiêu
Luyện tập thuật toán KMP (hàm prefix), Rabin-Karp (rolling hash) và áp dụng vào tìm kiếm mẫu trong chuỗi.
Yêu cầu
Bài 1: Xây dựng hàm Prefix (KMP)
Tính mảng prefix function (failure function) cho chuỗi pattern.
python
def compute_prefix(pattern: str) -> list[int]:
# prefix[i] = độ dài tiền tố thực sự dài nhất cũng là hậu tố của pattern[0..i]
pass
assert compute_prefix("AABAACAABAA") == [0,1,0,1,2,0,1,2,3,4,5]
assert compute_prefix("ABAB") == [0,0,1,2]Bài 2: Tìm kiếm KMP
Dùng prefix function để tìm tất cả vị trí xuất hiện của pattern trong text.
python
def kmp_search(text: str, pattern: str) -> list[int]:
# Tìm tất cả vị trí bắt đầu của pattern trong text
pass
assert kmp_search("AABAACAADAABAABA", "AABA") == [0, 9, 12]
assert kmp_search("ABCABC", "XYZ") == []Bài 3: Rabin-Karp Hash
Cài đặt thuật toán Rabin-Karp với rolling hash để tìm pattern trong text.
python
def rabin_karp(text: str, pattern: str, base: int = 256, mod: int = 101) -> list[int]:
# Tìm tất cả vị trí xuất hiện của pattern bằng rolling hash
pass
assert rabin_karp("ABABDABACDABABCABAB", "ABABCABAB") == [9]Bài 4: Ứng dụng - Đếm chuỗi con phân biệt
Cho chuỗi s và độ dài k, đếm số chuỗi con có độ dài k phân biệt sử dụng rolling hash.
python
def count_distinct_substrings(s: str, k: int) -> int:
# Đếm số chuỗi con độ dài k phân biệt trong s
pass
assert count_distinct_substrings("aababcab", 3) == 6Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Prefix | O(m) | O(m) |
| 2 - KMP | O(n + m) | O(m) |
| 3 - Rabin-Karp | O(n + m) avg | O(1) |
| 4 - Chuỗi con | O(n) avg | O(n) |
Gợi ý
Gợi ý Bài 1
Dùng hai con trỏ: i duyệt pattern, length theo dõi độ dài prefix. Khi mismatch, quay lại prefix[length-1].
Gợi ý Bài 3
Rolling hash: khi cửa sổ trượt, trừ hash ký tự cũ nhất và cộng ký tự mới. Dùng modular arithmetic. Khi hash trùng, so sánh chuỗi thực.
Gợi ý Bài 4
Dùng set lưu các giá trị hash. Với mỗi cửa sổ kích thước k, tính hash và thêm vào set. Kích thước set là kết quả.
Lời giải tham khảo
Xem lời giải
python
def compute_prefix(pattern: str) -> list[int]:
m = len(pattern)
prefix = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
prefix[i] = length
i += 1
elif length > 0:
length = prefix[length - 1]
else:
prefix[i] = 0
i += 1
return prefix
def kmp_search(text: str, pattern: str) -> list[int]:
if not pattern: return []
prefix = compute_prefix(pattern)
result = []
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]: j = prefix[j - 1]
if text[i] == pattern[j]: j += 1
if j == len(pattern):
result.append(i - j + 1)
j = prefix[j - 1]
return result
def rabin_karp(text, pattern, base=256, mod=101):
n, m = len(text), len(pattern)
if m > n: return []
result = []
p_hash = t_hash = 0
h = pow(base, m - 1, mod)
for i in range(m):
p_hash = (base * p_hash + ord(pattern[i])) % mod
t_hash = (base * t_hash + ord(text[i])) % mod
for i in range(n - m + 1):
if p_hash == t_hash and text[i:i+m] == pattern: result.append(i)
if i < n - m:
t_hash = (base * (t_hash - ord(text[i]) * h) + ord(text[i+m])) % mod
if t_hash < 0: t_hash += mod
return result