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.