Mini-challenge — tự viết grep bằng KMP

Bạn đang viết một công cụ dòng lệnh đơn giản giống grep: đọc một file văn bản, tìm tất cả vị trí mà một pattern xuất hiện, và in ra số dòng cùng offset. Khác với grep tiêu chuẩn chỉ in dòng đầu tiên khớp, công cụ của bạn phải báo cáo mọi vị trí — kể cả các lần xuất hiện chồng lấn (overlapping).

Bài toán này xuất hiện trong:

• Code search engine — tìm tất cả chỗ một function được gọi trong codebase lớn.
• Log analysis — tìm mọi lần một error code xuất hiện trong log file hàng GB.
• Bioinformatics — tìm mọi lần một đoạn gen ngắn xuất hiện trong chuỗi DNA — overlap là bình thường ("ATAT" có 2 lần "AT" chồng lấn).

Dành 20–25 phút tự implement trước khi xem gợi ý.

🎯 Đề bài

Viết hai hàm:

Hàm 1 — computeLPS(pattern)

• Input: chuỗi pattern độ dài m.
• Output: mảng lps[0..m-1] — failure function (longest proper prefix which is also suffix).

Hàm 2 — kmpSearchAll(text, pattern, lps)

• Input: chuỗi text độ dài n, chuỗi pattern độ dài m, mảng lps tính sẵn.
• Output: danh sách tất cả vị trí bắt đầu (0-indexed) mà pattern xuất hiện trong text, bao gồm cả trường hợp chồng lấn.

Ví dụ: text = "AAAA", pattern = "AA" → output [0, 1, 2] (ba lần xuất hiện chồng lấn).

📋 Test cases

Test case "AAAAAB" / "AAAAB" là input adversarial cho naive matching: tại mỗi vị trí i, naive khớp được 4 ký tự A rồi lệch ở B, buộc phải lùi về i+1 và so lại — worst-case O(n·m). KMP xử lý trong O(n+m) vì failure function lps của "AAAAB" là [0,1,2,3,0] — khi lệch tại B, nhảy j về 3 chứ không về 0.

📦 Concept mapping

Bài này luyện trực tiếp ba learning outcome của module:

▶️ Starter pseudocode

function computeLPS(pattern):
    m <- pattern.length
    lps[0..m-1] <- 0
    -- TODO: điền lps[1..m-1]
    -- Gợi ý: dùng con trỏ len = độ dài prefix-suffix đang khớp
    return lps

function kmpSearchAll(text, pattern, lps):
    results <- []
    -- TODO: quét text với hai con trỏ i (text) và j (pattern)
    -- Khi j = pattern.length: ghi nhận vị trí, reset j <- lps[j-1]
    -- Khi lệch và j > 0: j <- lps[j-1], i đứng yên
    -- Khi lệch và j = 0: i++
    return results

💡 Gợi ý

-- Xây mảng lineStart[i] = offset tuyệt đối bắt đầu dòng i
lineStart[0] <- 0
lineIdx <- 1
for k from 0 to text.length - 1:
    if text[k] = '\n':
        lineStart[lineIdx] <- k + 1
        lineIdx++

-- Với mỗi vị trí pos trong results: binary search lineStart tìm dòng

✅ Lời giải

function computeLPS(pattern):
    m <- pattern.length
    lps[0..m-1] <- 0        -- lps[0] luôn bằng 0
    len <- 0                 -- độ dài prefix-suffix đang khớp
    i <- 1

    while i < m:
        if pattern[i] = pattern[len]:   -- mở rộng được prefix-suffix
            len <- len + 1
            lps[i] <- len
            i <- i + 1
        else if len > 0:                -- lệch, lùi len về ứng viên ngắn hơn
            len <- lps[len-1]           -- KHÔNG tăng i
        else:                           -- len = 0, không còn ứng viên
            lps[i] <- 0
            i <- i + 1

    return lps
// Time: O(m)  Space: O(m)

function kmpSearchAll(text, pattern, lps):
    n <- text.length
    m <- pattern.length
    results <- []

    if m = 0: return results          -- pattern rỗng — không tìm

    i <- 0                            -- con trỏ text, CHỈ tăng
    j <- 0                            -- con trỏ pattern

    while i < n:
        if text[i] = pattern[j]:      -- khớp một ký tự
            i <- i + 1
            j <- j + 1
            if j = m:                 -- khớp hoàn toàn
                results.append(i - j) -- vị trí bắt đầu
                j <- lps[j-1]         -- reset để bắt overlap, KHÔNG về 0
        else if j > 0:                -- lệch nhưng đã khớp được j ký tự
            j <- lps[j-1]             -- dịch pattern, i đứng yên
        else:                         -- lệch ngay từ đầu
            i <- i + 1

    return results
// Time: O(n)  Space: O(1) ngoài mảng lps và results

function grepKMP(text, pattern):
    if pattern.length = 0: return []
    lps     <- computeLPS(pattern)
    results <- kmpSearchAll(text, pattern, lps)
    return results
// Time: O(n + m)  Space: O(m) cho lps

🎓 Mở rộng

Case-insensitive search: trước khi gọi grepKMP, chuyển cả text và pattern sang lowercase — O(n+m) tiền xử lý, không thay đổi logic matching.

Tìm nhiều pattern: nếu cần tìm đồng thời nhiều pattern trong cùng một text (ví dụ danh sách từ khoá), chạy KMP từng pattern sẽ là O(k × n + tổng_m) với k là số pattern. Khi k lớn (hàng nghìn pattern), đây không hiệu quả — đây chính là lý do Aho-Corasick tồn tại: xây trie một lần, duyệt text một lần O(n + tổng_m + k).

Đa dòng, báo cáo dạng grep: xây mảng lineStart như gợi ý Bước 3, binary search để ánh xạ offset → (line, col). Complexity tổng vẫn O(n+m) vì binary search là O(log n) trên mảng đã sắp xếp.

Wildcard matching (? khớp bất kỳ ký tự): KMP chuẩn không xử lý wildcard. Cần thuật toán khác (DP hoặc NFA simulation) — bài toán này phức tạp hơn đáng kể.

✨ Điều bạn vừa làm được

• Implement failure function computeLPS trong O(m) — cấu trúc dữ liệu cốt lõi của KMP.
• Viết kmpSearchAll với con trỏ text không bao giờ lùi — đảm bảo O(n) matching.
• Xử lý đúng trường hợp chồng lấn bằng reset j <- lps[j-1] thay vì j <- 0 sau khi tìm thấy.
• Kiểm chứng trên input adversarial "AAAA..." — nơi naive matching thật sự đạt O(n·m).
• Nhận ra giới hạn của KMP với đa pattern và hiểu khi nào cần chuyển sang Aho-Corasick.

Bài tiếp theo: Case study — Lucene index & ClamAV signature