Khi nào Rabin-Karp hiệu quả hơn so với KMP hoặc Boyer-Moore?
Khi nào Rabin-Karp hiệu quả hơn so với KMP hoặc Boyer-Moore?
Rabin–Karp dùng rolling hash so sánh hash của cửa sổ văn bản với hash mẫu rồi mới xác minh.
def rabin_karp(t, p, base=256, mod=10**9 + 7):
n, m = len(t), len(p)
if m > n: return -1
h = pow(base, m - 1, mod); hp = ht = 0
for i in range(m): hp = (hp * base + ord(p[i])) % mod; ht = (ht * base + ord(t[i])) % mod
for i in range(n - m + 1):
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.