Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi (tt) - Nguyễn Tri Tuấn

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi" cung cấp cho người đọc các kiến thức về thuật toán Rabin Karp. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi (tt) - Nguyễn Tri Tuấn Thuật toán Rabin Karp (1)
Tương tự như Brute Force
Tại mỗi vị trí i trên T, thay vì so sánh chi tiết từng ký tự P[j] với T[i+j] (chi phí O(M))
Sẽ so sánh hash(P, M) với hash(T, i, M) (chi phí O(1))
Tính hash(P, M)
hash(P, M) = P[0]*dM-1 + P[1]*dM-2 + ... + P[M-1]
Chi phí: O(M)
Tính hash(T, i, M)
T[i] đến T[i+(M-1)]
x = hash(T, i, M) = T[i]*dM-1 + T[i+1]*dM-2 + ... + T[i+(M-1)]
Chi phí: O(M) 13/38 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán Rabin Karp (2)
Làm sao tính hash(T, i+1, M) ?
Dịch chuyển sang phải một phần tử
y = hash(T, i+1, M) = (x - T[i]*dM-1)*d + T[i+M]
Chi phí: O(1) 14/38 CuuDuongThanCong.com https://fb.com/tailieudientucntt