Chuyên đề CNPM: Thuật toán đối sánh mẫu

1. Giới thiệu

Repo này chứa mã nguồn và tài liệu liên quan đến chuyên đề thuật toán tìm kiếm chuỗi (String Matching Algorithms).
Mục tiêu là cài đặt, phân loại và kiểm nghiệm hiệu năng các thuật toán.

2. Cấu trúc thư mục

• BAI TAP: Source code C++ các thuật toán
• TAI LIEU: Tài liệu tham khảo chính
• BAO CAO: Báo cáo + file phân loại và kiểm nghiệm (PDF)

3. Phân loại 35 thuật toán theo nhóm

Nhóm	Thuật toán
LTR - Left to Right (Trái sang phải)	Brute-force Karp and Rabin Shift-Or Morris-Pratt Knuth-Morris-Pratt Simon Deterministic Finite Automation Forward Dawg Matching Apostolico-Crochemore Not So Naive
RTL - Right to Left (Phải sang trái)	Boyer-Moore Apostolico-Giancarlo Turbo Boyer-Moore Reverse Colussi Reverse Factor Turbo Reverse Factor Backward Oracle Zhu-Takaoka Berry-Ravindran BNDM
SPE - Specific Order (Theo thứ tự xác định)	Galil-Seiferas Two-way Colussi Galil-Giancarlo Sunday Optimal Mismatch Maximal Shift Skip Search KMP Skip Search Alpha Skip Search String Matching on Ordered Alphabets
ANY - Any Position (Bất kỳ vị trí)	Horspool Quick Search Tuned Boyer-Moore Smith Raita

4. Các thuật toán được chọn để nghiên cứu

Các thuật toán trong repo được lựa chọn từ danh sách 35 thuật toán ban đầu, nhằm phục vụ việc cài đặt và kiểm nghiệm thuật toán.

Nhóm 20 thuật toán được chọn gồm:

Nhóm	Thuật toán
LTR	Karp and Rabin Shift-Or Morris-Pratt Knuth-Morris-Pratt Apostolico-Crochemore Not So Naive
RTL	Boyer-Moore Apostolico-Giancarlo Turbo Boyer-Moore Zhu-Takaoka Berry-Ravindran
SPE	Two-way Sunday Optimal Mismatch Maximal Shift Skip Search KMP Skip Search
ANY	Horspool Quick Search Tuned Boyer-Moore Smith Raita

5. Báo cáo

• Báo cáo chuyên đề (PDF)
• Bảng phân loại thuật toán
• File kiểm nghiệm thực nghiệm (PDF)