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

Một đồng nghiệp báo: "grep của mình chạy nhanh trên log thường, nhưng treo trên một file toàn chữ A". Bạn nghi ngờ naive, nhưng nghi ngờ chưa phải bằng chứng. Việc của lab này là dựng một công cụ tìm mọi vị trí của pattern trong text, kể cả các lần chồng lấn ("AAA" chứa "AA" ở vị trí 0 và 1, hai lần đè lên nhau), và gắn thêm một bộ đếm số phép so sánh ký tự để con số thay bạn trả lời: naive tệ đến đâu, KMP giữ được bao nhiêu.

Kiểu bài này hay gặp khi viết công cụ tìm kiếm trong code, lọc log, hoặc dò đoạn gen trong chuỗi DNA, nơi các lần khớp chồng lấn là chuyện thường. Dành 20–25 phút tự cài trước khi mở gợi ý.

Đề bài

Cài ba hàm. Hai hàm tìm kiếm đều trả về cặp (positions, comparisons).

• computeLPS(pattern): trả mảng lps[0..m-1] (failure function, xem bài KMP).
• findAllNaive(text, pattern): duyệt mọi cửa sổ, so từ trái sang phải, dừng ở ký tự lệch đầu tiên của cửa sổ đó.
• findAllKMP(text, pattern): dùng lps, con trỏ text không bao giờ lùi.

Quy tắc đếm (để hai bên đếm cùng một thước): mỗi lần đánh giá biểu thức text[x] = pattern[y] tính một phép so sánh, không tính phép so chỉ số hay phép gán. Cả hai hàm phải trả ([], 0) khi m = 0 hoặc m > n, không đụng vào text.

Ràng buộc:

• positions là danh sách vị trí bắt đầu, 0-indexed, tăng dần, gồm cả các lần chồng lấn.
• findAllKMP chạy O(n + m), và số phép so sánh của nó không vượt quá 2n. Nếu code của bạn vượt, con trỏ text đang lùi ở đâu đó.
• Quy ước pattern rỗng trả [] là lựa chọn của bài này (indexOf("") của Java trả 0). Thói quen liệt kê edge case trước khi code được dạy ở Edge case.

Trong test dưới, A^k nghĩa là chữ A lặp k lần.