Cấu trúc dữ liệu và Giải thuật Bài 53: Thuật toán KMP (Knuth-Morris-Pratt) - Tìm kiếm chuỗi con thần tốc.

Trong Bài 52, chúng ta đã dùng Trie để giải quyết bài toán tìm kiếm tiền tố cho hàng triệu từ khóa. Tuy nhiên, nếu bài toán đổi hướng: "Hãy tìm xem từ khóa has xuất hiện ở những vị trí nào bên trong một tệp log hệ thống dài 10 Gigabyte", Trie không còn là công cụ phù hợp. Chúng ta đang cần giải quyết bài toán Substring Search (Tìm kiếm chuỗi con) kinh điển.

Phản xạ tự nhiên nhất của lập trình viên là dùng thuật toán vét cạn (Brute-Force): Đặt chuỗi cần tìm áp sát vào văn bản, so sánh từng ký tự một. Nếu lệch ở đâu, nhích chuỗi lên 1 bước rồi so sánh lại từ đầu.

Thảm họa của cách này là độ phức tạp thời gian lên tới $O(N \times M)$ (với $N$ là độ dài văn bản, $M$ là độ dài chuỗi cần tìm). Khi văn bản chứa hàng tỷ ký tự, CPU sẽ lãng phí hàng triệu chu kỳ chỉ để so sánh lại những ký tự mà nó đã biết chắc chắn khớp từ trước.

Năm 1977, Donald Knuth, James H. Morris và Vaughan Pratt đã công bố một thuật toán thay đổi hoàn toàn cục diện tìm kiếm chuỗi: KMP Algorithm.

1. Tư duy thiên tài: Không bao giờ lùi bước con trỏ văn bản

Điểm yếu chí mạng của Brute-Force là mỗi lần gặp ký tự không khớp, nó bắt con trỏ duyệt văn bản (text index) quay đầu lùi lại phía sau để xét tiếp.

KMP tạo ra một cuộc cách mạng: Con trỏ duyệt văn bản (i) KHÔNG BAO GIỜ LÙI LẠI PHÍA SAU. Nó chỉ tiến thẳng hoặc đứng yên.

Làm thế nào KMP làm được điều kỳ diệu đó? Bí mật nằm ở việc nó tận dụng chính những thông tin đã khớp ở phần đầu chuỗi để biết chính xác mình nên dịch chuyển chuỗi cần tìm (pattern) đi bao nhiêu bước mà không bỏ sót bất kỳ một khả năng nào.

2. Trái tim của KMP: Mảng LPS (Longest Prefix Suffix)

Trước khi bắt đầu quét văn bản, KMP phân tích chuỗi cần tìm ($pattern$) để xây dựng một bảng phụ trợ gọi là Mảng LPS (Longest Proper Prefix which is also Suffix) hay còn gọi là Pi Array.

Ý nghĩa của LPS tại mỗi vị trí $i$: Độ dài của tiền tố (prefix) dài nhất đồng thời cũng là hậu tố (suffix) của chuỗi con kết thúc tại vị trí $i$ (không tính chính toàn bộ chuỗi).

Ví dụ: Xét chuỗi pattern = "ABABD"

• Tại i = 0 ('A'): Tiền tố/hậu tố rỗng $\rightarrow$ lps[0] = 0

• Tại i = 1 ('AB'): Không có tiền tố nào trùng hậu tố $\rightarrow$ lps[1] = 0

• Tại i = 2 ('ABA'): Tiền tố "A" trùng hậu tố "A", độ dài = 1 $\rightarrow$ lps[2] = 1

• Tại i = 3 ('ABAB'): Tiền tố "AB" trùng hậu tố "AB", độ dài = 2 $\rightarrow$ lps[3] = 2

• Tại i = 4 ('ABABD'): Không khớp $\rightarrow$ lps[4] = 0

Mảng LPS thu được: [0, 0, 1, 2, 0].

Khi xảy ra sự cố bất đồng ký tự tại vị trí $j$ trên chuỗi pattern, KMP không cần dò lại từ đầu mà nhìn thẳng vào lps[j-1] để biết con trỏ j nên nhảy về đâu ngay lập tức.

3. Triển khai Thuật toán KMP hoàn chỉnh bằng Golang

Đoạn mã dưới đây thực hiện hai nhiệm vụ: Xây dựng bảng LPS và quét văn bản tìm kiếm toàn bộ vị trí xuất hiện của chuỗi con.

Go

package main

import "fmt"

// 1. Xây dựng mảng LPS (Preprocessing Phase)
func computeLPS(pattern string) []int {
    m := len(pattern)
    lps := make([]int, m)
    length := 0 // Độ dài của prefix đồng thời là suffix dài nhất trước đó
    i := 1

    for i < m {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                // Thu hẹp phạm vi tìm kiếm dựa vào mảng LPS đã tính trước đó
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

// 2. Thuật toán tìm kiếm KMP chính thức
func KMPSearch(text string, pattern string) []int {
    n := len(text)
    m := len(pattern)
    if m == 0 {
        return nil
    }

    lps := computeLPS(pattern)
    var matches []int
    
    i := 0 // Con trỏ quét Text
    j := 0 // Con trỏ quét Pattern

    for i < n {
        if text[i] == pattern[j] {
            i++
            j++
        }

        if j == m {
            // Đã tìm thấy một khớp hoàn chỉnh tại vị trí (i - j)
            matches = append(matches, i-j)
            // Nhảy con trỏ j để tiếp tục tìm các kết quả tiếp theo chồng lấp
            j = lps[j-1]
        } else if i < n && text[i] != pattern[j] {
            // Không khớp, tận dụng mảng LPS để dịch chuyển pattern mà không lùi con trỏ i
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    return matches
}

4. Phân tích Hiệu năng: Đột phá $O(N + M)$

• Thời gian: $O(N + M)$ tuyệt đối. Quá trình tính toán mảng LPS tốn $O(m)$, và quá trình quét văn bản tốn $O(n)$ vì con trỏ văn bản i chỉ tiến về phía trước không bao giờ quay lui. Dù văn bản có dài đến đâu, KMP chỉ duyệt qua từng ký tự đúng một lần duy nhất.

• Không gian (RAM): $O(M)$ để lưu trữ mảng LPS của chuỗi cần tìm.

5. Ứng dụng thực chiến trong Kiến trúc Hệ thống

KMP không chỉ là bài toán lý thuyết trong sách giáo khoa, nó vận hành ngầm trong nhiều hệ thống hiệu năng cao:

• Công cụ grep và Log Parsers: Khi các hệ thống SIEM (Security Information and Event Management) quét hàng terabyte log hệ thống thời gian thực để tìm kiếm các chuỗi mẫu tấn công (như đoạn mã SQL Injection hay XSS), các công cụ biên dịch dòng lệnh sử dụng tối ưu hóa của KMP để tăng tốc độ phân tích.

• Phần mềm soạn thảo văn bản (Text Editors): Tính năng "Find & Replace" siêu tốc trong VS Code hay các IDE lớn sử dụng các thuật toán xử lý chuỗi tối ưu tương tự KMP để tìm kiếm từ khóa trong file mã nguồn mà không làm đơ giao diện UI.

• Tin sinh học (Bioinformatics): So khớp các chuỗi DNA/RNA dài hàng triệu cặp nucleotide trong chuỗi gen của sinh vật học phân tử.

Khép lại chương về chuỗi ký tự, chúng ta đã đi từ việc cấu trúc từ vựng bằng Trie cho đến tối ưu hóa tốc độ tìm kiếm văn bản bằng KMP. Tuy nhiên, trong thế giới lập trình backend, đôi khi bạn phải đối mặt với những bài toán tối ưu tổ hợp phức tạp — nơi số lượng phương án giải quyết bùng nổ theo cấp số nhân và không có cấu trúc dữ liệu nào có thể lưu trữ nổi. Đó là lúc chúng ta phải bước vào thế giới chiến lược của Lập trình động (Dynamic Programming).