Mô phỏng thuật toán Băm chuỗi (hash đa thức)

Polynomial String Hashing · Nhóm: Chuỗi

Băm chuỗi (hash đa thức) (Polynomial String Hashing), nhóm Chuỗi.

Mã Python

def poly_hash_search(s, pat):
    h_pat = compute_hash(pat)
    h_win = compute_hash(s[:m])
    for i in range(len(s) - m + 1):
        if h_win != h_pat:           # hash differs: skip
            pass
        elif s[i:i+m] == pat:        # hash matches: verify chars
            return i
        if i + m < len(s):           # rolling hash O(1)
            h_win = roll(h_win, s[i], s[i+m])
    return -1

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.