Thuật toán Knuth Morris Pratt (KMP) là thuật toán hiệu quả tìm chuỗi con (chuỗi mẫu - pattern) bên trong chuỗi cha.
Bài toán
Cho 1 chuỗi mẫu pattern P độ dài m và đoạn text T độ dài n, tìm tất cả các lần mà chuỗi P xuất hiện bên trong đoạn text T. Ta có thể coi n > m.
Cách giải đơn thuần (naive solution)
Dùng 2 vòng lặp
- Thử lần lượt từng vị trí trên T (n - m + 1 vị trí [0...n - m])
- Với từng vị trí trên T, thử khớp P bắt đầu từ vị trí này (m kí tự), cho đến khi khớp hoàn toàn hoặc gặp kí tự sai khác.