KMP: failure function & matching O(n+m)

TL;DR: Naive matching lãng phí vì mỗi lần lệch nó quay con trỏ text về và so lại từ đầu. KMP loại bỏ lãng phí đó bằng failure function (còn gọi prefix function) lps[i]: độ dài của tiền tố thực sự dài nhất của pattern[0..i] mà đồng thời cũng là hậu tố (tiền tố là phần đầu, hậu tố là phần đuôi, "thực sự" nghĩa là không lấy cả chuỗi). Khi lệch tại vị trí j của pattern, thay vì lùi text, ta dịch pattern về lps[j-1], vì phần đầu pattern đến đó chắc chắn đã khớp. Con trỏ text không bao giờ lùi, nên matching chạy O(n). Xây bảng failure cũng O(m) bằng chính ý tưởng đó. Tổng O(n+m), so với O(n·m) của naive.

Ở bài trước bạn thấy naive matching đạt worst-case O(n·m): với text "aaaa...a" và pattern "aaa...ab", mỗi vị trí khởi đầu so gần hết pattern rồi lệch ở ký tự cuối, rồi lùi con trỏ text về so lại. KMP (Knuth-Morris-Pratt, 1977) hỏi: khi đã so khớp được j ký tự rồi mới lệch, chẳng phải ta đã biết j ký tự đó là gì sao? Tại sao phải so lại?

Bối cảnh thực tế: String.indexOf, lệnh grep tìm chuỗi cố định, hay LIKE '%abc%' trong SQL (xem bài LIKE và pattern matching) đều giải bài toán "tìm pattern trong text" này, dù mỗi nơi chọn thuật toán riêng.

1. Vì sao naive lãng phí, và KMP tận dụng gì

Xét text T = "ABABABABC" và pattern P = "ABABC".

Naive khớp được ABAB (4 ký tự) rồi lệch tại T[4]='A' vs P[4]='C'. Phản ứng của naive: dịch pattern sang đúng 1 ô, đưa con trỏ text lùi về T[1], so lại từ P[0].

Nhưng ta vừa biết T[0..3] = "ABAB". Bên trong "ABAB", tiền tố "AB" trùng với hậu tố "AB". Nghĩa là sau khi lệch, ta có thể dịch pattern sao cho P[0..1]="AB" thẳng hàng ngay với hậu tố "AB" của đoạn vừa khớp. Không cần so lại hai ký tự đó, và con trỏ text đứng yên tại T[4].

2. Failure function: định nghĩa chính xác

Hình dung bạn đọc thuộc một bài thơ có điệp khúc. Đang đọc thì quên lời, bạn không quay về câu đầu bài: bạn nhận ra điệp khúc vừa đọc xong cũng chính là phần đầu của đoạn kế, rồi nối tiếp từ đó.

Phần đầu của một chuỗi gọi là tiền tố, phần đuôi gọi là hậu tố; con số "đoạn lặp dài nhất ở hai đầu" cho từng vị trí của pattern gọi là lps.

Failure function (hay prefix function) của pattern P độ dài m là mảng lps[0..m-1] (lps = longest proper prefix which is also suffix):

lps[i] = độ dài của tiền tố thực sự dài nhất của chuỗi con P[0..i] mà đồng thời là hậu tố của P[0..i].

"Tiền tố thực sự" (proper prefix) = tiền tố không phải toàn bộ chuỗi (độ dài tối đa i, không phải i+1). Nếu cho phép lấy cả chuỗi thì đáp án luôn là chính nó, vô nghĩa.

Ví dụ P = "ABABC":

Đọc lps[3]=2 nghĩa là: trong "ABAB", hai ký tự đầu "AB" trùng với hai ký tự cuối "AB". Con số 2 này cho phép KMP dịch pattern thông minh khi lệch sau khi đã khớp 4 ký tự.

lps là thuộc tính nội tại của pattern, tính xong trước khi nhìn thấy text.