Thuật toán KMP tìm vị trí xuất hiện của xâu mẫu

Mục tiêu kiến thức

• Xây dựng mảng tiền tố π (Prefix Function / LPS - Longest Proper Prefix which is also Suffix).
• Nắm vững cơ chế nhảy con trỏ khi không khớp (mismatch) mà không cần quay lui con trỏ trên văn bản gốc.
• Đạt độ phức tạp thời gian tuyến tính nghiêm ngặt O(N + M) loại bỏ trường hợp xấu nhất O(N × M) của tìm kiếm ngây thơ.

Mô tả bài toán

Trong hệ thống quét mẫu dữ liệu độc hại và lọc từ khóa của AI Empire Academy, ta cần tìm kiếm tất cả các vị trí xuất hiện của một chuỗi mẫu pattern trong một đoạn văn bản dài text.

Cho hai chuỗi text và pattern. Hãy viết hàm kmp_search(text: str, pattern: str) -> list[int] trả về danh sách gồm tất cả các chỉ số 0-based bắt đầu của pattern xuất hiện trong text.

Quy tắc:

• Kết quả trả về là danh sách các số nguyên tăng dần biểu thị vị trí bắt đầu (0-based).
• Các lần xuất hiện có thể chồng lấn lên nhau (Overlapping matches). Ví dụ: text = "AAAA", pattern = "AA" ⇒ Kết quả là [0, 1, 2].
• Nếu pattern rỗng hoặc không tìm thấy lần xuất hiện nào, trả về danh sách rỗng [].
• Thuật toán bắt buộc phải cài đặt theo chuẩn Knuth-Morris-Pratt (KMP) với độ phức tạp O(|text| + |pattern|).

Ràng buộc

• 0 ≤ |text| ≤ 10⁵.
• 0 ≤ |pattern| ≤ 10⁴.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.