Bản chất của thuật toán KMP

Thuật toán Knuth-Morris-Pratt (KMP) thường được coi là một trong những thuật toán khó tiếp cận đối với người mới bắt đầu. Tuy nhiên, rào cản lớn nhất không nằm ở logic tìm kiếm mà nằm ở việc hiểu rõ cấu trúc dữ liệu nền tảng của nó: Partial Match Table (PMT) hay Bảng khớp một phần.

Để hiểu KMP, chúng ta cần nắm vững hai khái niệm: Tiền tố (Prefix) và Hậu tố (Suffix).

• Tiền tố: Là tập hợp các chuỗi con bắt đầu từ ký tự đầu tiên của chuỗi gốc nhưng không bao gồm chính nó. Ví dụ, với chuỗi "ALGO", tiền tố gồm {"A", "AL", "ALG"}.
• Hậu tố: Là tập hợp các chuỗi con kết thúc tại ký tự cuối cùng của chuỗi gốc nhưng không bao gồm chính nó. Với chuỗi "ALGO", hậu tố gồm {"LGO", "GO", "O"}.

Giá trị trong bảng PMT tại một vị trí cụ thể chính là độ dài của chuỗi con dài nhất vừa là tiền tố, vừa là hậu tố của chuỗi tính đến vị trí đó.

Phân tích ví dụ cụ thể

Xét chuỗi mẫu (pattern) "abababca". Bảng PMT của nó được tính toán như sau:

Tại chỉ số 4 (chuỗi "ababa"), tiền tố là {"a", "ab", "aba", "abab"} và hậu tố là {"baba", "aba", "ba", "a"}. Giao điểm của hai tập hợp này là {"a", "aba"}. Chuỗi dài nhất là "aba" với độ dài bằng 3. Do đó, PMT[4] = 3.

Sử dụng mảng next để tối ưu hóa

Trong lập trình thực tế, để thuận tiện cho việc xử lý chỉ số khi xảy ra sai khác (mismatch), chúng ta thường dịch chuyển bảng PMT sang phải một đơn vị và gán giá trị đầu tiên là -1. Mảng mới này được gọi là mảng next.

Khi so khớp chuỗi mẫu với chuỗi văn bản, nếu xảy ra lỗi tại vị trí j, chúng ta không cần quay lại từ đầu. Thay vào đó, chúng ta biết rằng phần trước đó đã khớp, và dựa vào mảng next, ta có thể trượt chuỗi mẫu đến vị trí khớp tiềm năng tiếp theo một cách thông minh.

Triển khai mã nguồn

Dưới đây là hàm thực thi tìm kiếm KMP. Thay vì so sánh lại từ đầu, ta tận dụng mảng jumpTable (tương đương mảng next) để dịch chuyển con trỏ chuỗi mẫu.

int findSubstringKMP(char *haystack, char *needle, int *jumpTable) {
    int textLen = strlen(haystack);
    int patLen = strlen(needle);
    int i = 0; // Chỉ số cho haystack
    int j = 0; // Chỉ số cho needle

    while (i < textLen && j < patLen) {
        if (j == -1 || haystack[i] == needle[j]) {
            i++;
            j++;
        } else {
            // Nhảy đến vị trí khớp tiếp theo dựa trên bảng đã tính
            j = jumpTable[j];
        }
    }

    if (j == patLen) {
        return i - j; // Trả về vị trí bắt đầu tìm thấy
    }
    return -1;
}

Xây dựng mảng hỗ trợ nhảy (Next Array)

Việc tạo mảng next thực chất là một quá trình tự so khớp (self-matching). Chúng ta coi tiền tố của chuỗi mẫu là một mục tiêu tìm kiếm bên trong chính chuỗi mẫu đó.

void buildJumpTable(char *pattern, int *next) {
    int len = strlen(pattern);
    next[0] = -1;
    int curr = 0;
    int prevMatch = -1;

    while (curr < len - 1) {
        if (prevMatch == -1 || pattern[curr] == pattern[prevMatch]) {
            curr++;
            prevMatch++;
            next[curr] = prevMatch;
        } else {
            // Quay lui về vị trí khớp ngắn hơn trước đó
            prevMatch = next[prevMatch];
        }
    }
}

KMP giúp giảm độ phức tạp thời gian xuống O(n + m), trong đó n là độ dài văn bản và m là độ dài chuỗi mẫu. Bằng cách loại bỏ các bước so sánh thừa thãi thông qua việc hiểu rõ tính chất đối xứng của chuỗi con, KMP trở thành một công cụ mạnh mẽ trong các bài toán xử lý văn bản quy mô lớn.