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ố. 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 một câu sắc bén: 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 này giải thích failure function — cấu trúc cho phép tái dùng thông tin đã khớp để không bao giờ lùi text — cách xây nó, vì sao nó đúng, và trace đầy đủ.

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

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). Điều này quan trọng: 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". Chính 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ự.

3. Matching: dùng lps để không bao giờ lùi text

Ý tưởng: dùng hai con trỏ — i quét text (không bao giờ giảm), j chỉ vị trí đang so trong pattern. Khi khớp, cả hai tiến. Khi lệch và j vẫn đang dương, ta không lùi i mà chỉ kéo j về lps[j-1].

function KMPSearch(T, P, lps):       -- T text độ dài n, P pattern độ dài m
    i <- 0                            -- con tro text, KHONG bao gio giam
    j <- 0                            -- con tro pattern
    while i < T.length:
        if T[i] = P[j]:               -- khop mot ky tu
            i <- i + 1
            j <- j + 1
            if j = P.length:          -- khop het pattern
                báo tìm thấy tại vị trí i - j
                j <- lps[j-1]         -- tiep tuc tim lan xuat hien ke
        else if j > 0:                -- lech, nhung da khop duoc j ky tu
            j <- lps[j-1]             -- dich pattern, i dung yen
        else:                         -- lech ngay ky tu dau (j = 0)
            i <- i + 1
    return
// Time: O(n)  Space: O(1) ngoai bang lps

Điểm mấu chốt nằm ở nhánh else if j > 0: khi lệch, ta đã biết T[i-j .. i-1] khớp P[0..j-1]. Kéo j về lps[j-1] tương đương dịch pattern sao cho tiền tố dài lps[j-1] (đã chắc chắn khớp với hậu tố vừa rồi) thẳng hàng, rồi so tiếp từ vị trí j mới mà không đụng lại text cũ.

3.1 Trace T = "ABABABABC", P = "ABABC"

lps = [0, 0, 1, 2, 0].

Để ý: con trỏ i chỉ tăng, chưa bao giờ lùi. Ở bước 5 và 8, khi lệch ta nhảy j từ 4 về 2 mà giữ nguyên i — đây chính là chỗ KMP tiết kiệm so với naive (naive sẽ lùi i về và so lại từng vị trí).

flowchart LR
    START(["i=0, j=0"]) --> MATCH{"T[i] = P[j]?"}
    MATCH -->|"đúng"| ADV["i++, j++"]
    ADV --> FULL{"j = m?"}
    FULL -->|"đúng"| FOUND(["báo khớp; j <- lps[j-1]"])
    FULL -->|"chưa"| MATCH
    MATCH -->|"sai, j>0"| JUMP["j <- lps[j-1] (i đứng yên)"]
    JUMP --> MATCH
    MATCH -->|"sai, j=0"| SKIP["i++"]
    SKIP --> MATCH
    FOUND --> MATCH

4. Xây bảng lps trong O(m)

Mẹo hay nhất của KMP: xây bảng lps bằng chính KMP áp lên pattern so với chính nó. Ta duyệt P và giữ một con trỏ len = độ dài đoạn prefix-suffix khớp hiện tại.

function computeLPS(P):
    lps[0] <- 0                       -- proper prefix cua 1 ky tu luon rong
    len <- 0                          -- do dai prefix-suffix dang khop
    i <- 1
    while i < P.length:
        if P[i] = P[len]:             -- mo rong duoc doan prefix-suffix
            len <- len + 1
            lps[i] <- len
            i <- i + 1
        else if len > 0:              -- lech: lui len ve lps cua chinh no
            len <- lps[len-1]         -- KHONG tang i
        else:                         -- len = 0, khong co prefix-suffix
            lps[i] <- 0
            i <- i + 1
    return lps
// Time: O(m)  Space: O(m)

Nhánh else if len > 0 lùi len <- lps[len-1] chính là phép "dịch pattern" áp lên bản thân pattern: nếu không mở rộng được prefix-suffix dài len, thử prefix-suffix ngắn hơn — mà độ dài ngắn hơn đó lại do lps của đoạn đã tính nắm giữ. Đệ quy trên lps đúng vì một prefix-suffix ngắn hơn của P[0..i] phải là prefix-suffix của prefix-suffix dài hơn.

4.1 Trace computeLPS("ABABC")

Kết quả lps = [0,0,1,2,0] — khớp bảng định nghĩa ở phần 2.

5. Vì sao tổng độ phức tạp là O(n+m)

Thoạt nhìn vòng while của matching có nhánh j <- lps[j-1] không tăng i — liệu nó lặp vô hạn hay làm xấu độ phức tạp?

Phân tích amortized (xem amortized analysis): mỗi vòng lặp hoặc tăng i (tối đa n lần) hoặc giảm j (qua j <- lps[j-1]). Mà j chỉ tăng khi i tăng (cùng nhánh khớp), nên tổng số lần tăng j tối đa bằng tổng số lần tăng i, tức n. Số lần giảm j không thể vượt số lần tăng j. Vậy tổng số bước bị chặn bởi 2n = O(n). Tương tự computeLPS là O(m). Tổng O(n+m).

So sánh trực tiếp:

6. Pitfall

Pitfall 1 — Nhầm lps là "khớp tới đâu" thay vì "prefix = suffix"

-- SAI: tuong lps[i] = so ky tu da khop tinh tu dau
-- Dan toi dich pattern sai khi lech

lps[i] không phải số ký tự đã khớp với text — nó là thuộc tính nội tại của pattern (prefix trùng suffix), tính trước khi nhìn text. Lẫn lộn hai khái niệm này dẫn đến dịch pattern sai hoặc bỏ sót lần xuất hiện.

Pitfall 2 — Lùi len rồi quên không tăng i trong computeLPS

-- SAI: trong nhanh lech van tang i
else if len > 0:
    len <- lps[len-1]
    i <- i + 1            -- BUG: lam mat co hoi so P[i] voi prefix ngan hon

-- DUNG: chi lui len, GIU nguyen i de so lai P[i] voi prefix ngan hon
else if len > 0:
    len <- lps[len-1]

Tăng i ở nhánh lệch khiến ta bỏ qua việc thử khớp P[i] với một prefix-suffix ngắn hơn — bảng lps sai, kéo theo matching sai.

Pitfall 3 — Sau khi tìm thấy, quên reset j <- lps[j-1] để tìm lần kế

-- Neu chi return ngay khi j = m, ta bo sot cac lan xuat hien chong lan
-- Vi du P="aa", T="aaaa" co 3 lan xuat hien tai 0,1,2
if j = P.length:
    báo tìm thấy tại i - j
    j <- lps[j-1]        -- tiep tuc, khong return

Với pattern tự chồng lấn (như "aa" trong "aaaa"), reset j về lps[j-1] cho phép bắt mọi lần xuất hiện kể cả khi chúng overlap.

7. Liên hệ các bài khác

• Naive string matching: KMP sinh ra để vá đúng điểm lãng phí của naive — đọc bài đó trước để thấy rõ "lùi text rồi so lại" tốn kém ra sao.
• Rabin-Karp: Hướng tiếp cận khác — dùng rolling hash thay vì failure function. KMP đảm bảo O(n+m) tất định; Rabin-Karp O(n+m) kỳ vọng nhưng mở rộng tốt cho đa mẫu.
• Z-function: Một cấu trúc prefix khác (độ dài đoạn từ vị trí i trùng với prefix). Z-function và failure function chuyển đổi được cho nhau và giải cùng lớp bài.
• Aho-Corasick: Tổng quát hoá failure function lên một trie nhiều pattern — "failure link" trên cây chính là lps đa mẫu.
• Amortized analysis: Công cụ để chứng minh vòng lặp có bước "lùi j" vẫn tổng O(n).

📚 Deep Dive

Tóm tắt

• Naive lãng phí vì lùi con trỏ text và so lại đoạn đã biết; KMP loại bỏ hoàn toàn việc lùi text.
• Failure function lps[i] = độ dài tiền tố thực sự dài nhất của P[0..i] mà cũng là hậu tố — thuộc tính nội tại của pattern.
• Khi lệch tại j > 0, kéo j <- lps[j-1] thay vì lùi i — dịch pattern để tiền tố đã-chắc-chắn-khớp thẳng hàng.
• Bảng lps xây trong O(m) bằng cách áp chính ý tưởng KMP lên pattern so với chính nó.
• Tổng O(n+m) chứng minh bằng amortized: số lần giảm j không vượt số lần tăng j, mà số lần tăng j bị chặn bởi n.
• Reset j <- lps[j-1] sau khi khớp đủ để bắt cả các lần xuất hiện chồng lấn.

Tự kiểm tra

Bài tiếp theo: Rabin-Karp — rolling hash cho đa mẫu