1. Giới thiệu:
a. Hoàn cảnh:
Một lớp những bài toán rất được quan tâm trong khoa học máy tính nói chung và lập
trình thi cử nói riêng, đó là xử lý xâu chuỗi. Trong lớp bài toán này, người ta thường rất hay
phải đối mặt với một bài toán: tìm kiếm xâu chuỗi.
b. Phát biểu bài toán:
i. Cho một đoạn văn bản, gồm � ký tự.
ii. Cho một đoạn mẫu, gồm � ký tự.
iii. Máy tính cần trả lời câu hỏi: đoạn mẫu xuất hiện bao nhiêu lần trong
đoạn văn bản và chỉ ra các vị trí xuất hiện đó.
c. Thuật toán:
Có rất nhiều thuật toán có thể giải quyết bài toán này. Người viết xin tóm
tắt 2 thuật toán phổ biến được dùng trong các kì thi lập trình:
i. Brute-force approach:
Với một cách tiếp cận trực tiếp, chúng ta có thể thu được thuật toán để
giải. Tuy nhiên độ phực tạp của nó là rất lớn trong trường hợp xấu nhất.
Thuật toán brute-force so khớp tất cả các vị trí xuất hiện của đoạn mẫu
trong đoạn văn bản. Cụ thể độ phức tạp cho thuật toán này là �(��).
ii. Knuth-Morris-Pratt algorithm
Hay còn được viết tắt là KMP, được phát minh vào năm 1974, bởi
Donald Knuth, Vaughan Pratt và James H. Morris. Thuật toán này sử
dụng một correction-array, là một thuật toán rất hiệu quả, có độ phức
tạp là �(� + �).
d. Mục đích bài viết:
Trong bài viết này, người viết chỉ tập trung vào một thuật toán. Tác giả xin gọi thuật toán
này là Hash. Theo như bản thân người viết đánh giá, đây là thuật toán rất hiệu quả đặc biệt
là trong thi cử. Nó hiệu quả bởi 3 yếu tố: tốc độ thực thi, linh động trong việc sử dụng (ứng
dụng hiệu quả) và sự đơn giản trong cài đặt.
Đầu tiên, người viết xin được trình bày về thuật toán này. Sau đó, người viết sẽ trình bày
một vài ứng dụng, cách sử dụng và phát triển thuật toán Hash trong các bài toán tin học.
2. Thuật toán Hash:
a. Ký hiệu:
i. Tập hợp các chữ cái được sử dụng: Σ