Lesson 41 — KMP (Knuth-Morris-Pratt)
Tìm pattern trong text với O(n+m) — text pointer không bao giờ lùi. Trái tim là mảng LPS (failure function).
1. LPS Builder (failure function)
lps[i] = độ dài proper prefix dài nhất của P[0..i] mà đồng thời là suffix. Hai con trỏ:
i (đang xét) và
len (độ dài prefix-suffix).
Pattern:
Nhấn “Bước tiếp” để bắt đầu tính LPS.
2. KMP Matching
Khi mismatch tại P[j] với j>0: nhảy j = lps[j-1] — text pointer i đứng yên. Khi tìm thấy: ghi match, j = lps[j-1] để bắt overlap.
Text:
Pattern:
LPS của pattern:
Text (con trỏ i):
Pattern (con trỏ j) — căn theo i-j:
Nhấn “Bước tiếp” để chạy KMP.
3. Naive vs KMP (số phép so sánh)
Cùng input, đếm tổng số phép so sánh ký tự. Naive lùi text mỗi mismatch; KMP không.
Thử: chạy trên text có prefix lặp nhiều — naive quay lui liên tục, KMP không bao giờ lùi con trỏ text: đếm phép so sánh để thấy chênh.
Text:
Pattern:
Naive O(nm)
—
phép so sánh
KMP O(n+m)
—
phép so sánh
Nhấn “So sánh” để đo.