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).
Module 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.
Module 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.
Module 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.
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.