Các thuật toán so khớp chuỗi chính xác

Bộ tài liệu tiếng Việt về 36 thuật toán so khớp chuỗi chính xác (exact string matching): tìm mọi vị trí xuất hiện của một mẫu x độ dài m trong văn bản y độ dài n.

Nội dung do Claude biên soạn cho mục đích học tập, lấy cảm hứng từ danh mục thuật toán kinh điển trong lĩnh vực so khớp chuỗi (Charras & Lecroq). Mọi văn bản và mã nguồn trong bộ tài liệu này đều được viết mới.

Mục lục

1. Giới thiệu
2. Brute Force (vét cạn)
3. Otomat hữu hạn đơn định (DFA)
4. Karp-Rabin
5. Shift-Or
6. Morris-Pratt
7. Knuth-Morris-Pratt
8. Simon
9. Colussi
10. Galil-Giancarlo
11. Apostolico-Crochemore
12. Not So Naive
13. Boyer-Moore
14. Turbo Boyer-Moore
15. Apostolico-Giancarlo
16. Reverse Colussi
17. Horspool
18. Quick Search
19. Tuned Boyer-Moore
20. Zhu-Takaoka
21. Berry-Ravindran
22. Smith
23. Raita
24. Reverse Factor (BDM)
25. Turbo Reverse Factor
26. Forward Dawg Matching
27. BNDM
28. Backward Oracle Matching
29. Galil-Seiferas
30. Two Way
31. So khớp trên bảng chữ có thứ tự
32. Optimal Mismatch
33. Maximal Shift
34. Skip Search
35. KMP Skip Search
36. Alpha Skip Search

Cấu trúc mỗi bài

Mỗi thuật toán (từ mục 2 trở đi) gồm: Đặc điểm chính (độ phức tạp tiền xử lý / tìm kiếm, bộ nhớ phụ, hướng so sánh), Ý tưởng, Mô tả chi tiết, Cài đặt bằng C, Ví dụ minh họa và Tài liệu tham khảo.