\(KMP\) (Knuth-Morris-Pratt) là một thuật toán hiệu quả để tìm kiếm chuỗi con trong chuỗi lớn. Được phát triển bởi Donald Knuth, Vaughan Pratt và James H. Morris, thuật toán này cải thiện hiệu suất so với các phương pháp tìm kiếm truyền thống bằng cách sử dụng thông tin về sự trùng lặp của chuỗi.

\(KMP\) hoạt động thông qua việc xây dựng một bảng “prefix” (tiền tố), cho phép thuật toán bỏ qua các ký tự đã khớp mà không cần quay lại chuỗi chính. Điều này giúp giảm thiểu số lần so sánh ký tự, đạt thời gian thực hiện là \(O(n + m)\), trong đó \(n\) là chiều dài chuỗi chính và \(m\) là chiều dài chuỗi con.

Thuật toán \(KMP\) rất hữu ích trong các ứng dụng như tìm kiếm văn bản, xử lý ngôn ngữ tự nhiên và các hệ thống thông tin. Nhờ vào tính hiệu quả và linh hoạt, \(KMP\) đã trở thành một trong những thuật toán tìm kiếm chuỗi phổ biến nhất trong lập trình và khoa học máy tính.

Minh họa:

Để minh họa chi tiết thuật toán, chúng ta sẽ tìm hiểu từng quá trình thực hiện của thuật toán. Ở mỗi thời điểm, thuật toán luôn được xác định bằng hai biến kiểu nguyên, \(m\) và \(i\), được định nghĩa lần lượt là vị trí tương ứng trên \(S\) bắt đầu cho một phép so sánh với \(W\), và chỉ số trên \(W\) xác định ký tự đang được so sánh. Khi bắt đầu, thuật toán được xác định như sau:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      0

Chúng ta tiến hành so sánh các ký tự của \(W\) tương ứng với các ký tự của \(S\), di chuyển lần lượt sang các chữ cái tiếp theo nếu chúng giống nhau. \(S[0]\) và \(W[0]\) đều là \(‘A’\). Ta tăng \(i\):

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      _1  

\(S[1]\) và \(W[1]\) đều là \(‘B’\). Ta tiếp tục tăng \(i\):

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      __2 

\(S[2]\) và \(W[2]\) đều là \(‘C’\). Ta tăng \(i\) lên 3:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      ___3  

Nhưng, trong bước thứ tư, ta thấy \(S[3]\) là một khoảng trống trong khi \(W[3]=’D’\), không phù hợp. Thay vì tiếp tục so sánh lại ở vị trí \(S[1]\), ta nhận thấy rằng không có ký tự ‘A’ xuất hiện trong khoảng từ vị trí 0 đến vị trí 3 trên xâu S ngoài trừ vị trí 0; do đó, nhờ vào quá trình so sánh các ký tự trước đó, chúng ta thấy rằng không có khả năng tìm thấy xâu dù có so sánh lại. Vì vậy, chúng ta di chuyển đến ký tự tiếp theo, gán \(m=4\) và i=0.

m: ____4
S:      ABC ABCDAB ABCDABCDABDE
W:          ABCDABD
i:          0 

Tiếp tục quá trình so sánh như trên, ta xác định được xâu chung “ABCDAB”, với W[6] (S[10]), ta lại thấy không phù hợp. Nhưng từ kết quả của quá trình so sánh trước, ta đã duyệt qua “AB”, có khả năng sẽ là khởi đầu cho một đoạn xâu khớp, vì vậy ta bắt đầu so sanh từ vị trí này. Như chúng ta đã thấy các ký tự này đã trùng khớp với nhau ký tự trong phép so khớp trước, chúng ta không cần kiểm tra lại chúng một lần nữa; ta bắt đầu với m = 8, i = 2 và tiếp tục quá trình so khớp.

m: ________8
S:      ABC ABCDAB ABCDABCDABDE
W:              ABCDABD
i:              __2

Quá trình so khớp ngay lập tức thất bại, nhưng trong W không xuất hiện ký tự ‘ ‘,vì vậy, ta tăng m lên 11, và gán i = 0.

m:         ___________11
S:      ABC ABCDAB ABCDABCDABDE
W:                 ABCDABD
i:                 0

Một lần nữa, hai xâu trùng khớp đoạn ký tự “ABCDAB” nhưng ở ký tự tiếp theo, ‘C’, không trùng với ‘D’ trong W. Giống như trước, ta gán m = 15, và gán i = 2, và tiếp tục so sánh.

m:         _______________15
S:      ABC ABCDAB ABCDABCDABDE
W:                     ABCDABD
i:                     __2

Lần này, chúng ta đã tìm được khớp tương ứng với vị trí bắt đầu là S[15].

Thuật toán và mã giả của thuật toán tìm kiếm KMP

Bây giờ, chúng ta tìm hiểu về sự tồn tại của bảng “so khớp một phần”(partial match) \(T\), được mô tả bên dưới, giúp ta xác định được vị trí tiếp theo để so khớp khi phép so khớp trước đã thất bại. Mảng \(T\) được tổ chức để nếu chúng ta có một phép so khớp bắt đầu từ \(S[m]\) thất bại khi so sánh \(S[m\) + \(i]\) với \(W[i]\), thì vị trí của phép so khớp tiếp theo có chỉ số là m + i – T[i] trong \(S\) (\(T[i]\) là đại lượng xác định số ô cần lùi khi có một phép so khớp thất bại). Mặc dù phép so khớp tiếp theo sẽ bắt đầu ở chỉ số m + i – T[i], giống như ví dụ ở trên, chúng ta không cần so sánh các ký tự \(T[i]\) sau nó, vì vậy chúng ta chỉ cần tiếp tục so sánh từ ký tự \(W[T[i]]\). Ta có \(T[0]\) \(=\) \(-1\), cho thấy rằng nếu \(W[0]\) không khớp, ta không phải lùi lại mà tiếp tục phép so sánh mới ở ký tự tiếp theo. Sau đây là đoạn mã giả mẫu của thuật toán tìm kiếm \(KMP\).

algorithm kmp_search:
    input:
        mảng ký tự, S (đoạn văn bản)
        mảng ký tự, W (xâu đang tìm)
    output:
        một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

    define variables:
        biến nguyên, m ← 0 
        biến nguyên, i ← 0 
        mảng nguyên, T 

    while m + i nhỏ hơn độ dài của sâu S, do:
        if W[i] = S[m + i],
            let i ← i + 1
            if i bằng độ dài W,
                return m
        otherwise,
            if T[i] > -1,
                let i ← T[i], m ← m + i - T[i]
            else
                let i ← 0, m ← m + 1
            
    return độ dài của đoạn văn bản S

Độ phức tạp của thuật toán tìm kiếm KMP

Với sự xuất hiện của mảng \(T\), phần tìm kiếm của thuật toán Knuth–Morris–Pratt có độ phức tạp \(O(k)\), trong đó k là độ dài của xâu \(S\). Ngoại trừ các thủ tục nhập xuất hàm ban đầu, tất cả các phép toán đều được thực hiện trong vòng lặp \(while\), chúng ta sẽ tính số câu lệnh được thực hiện trong vòng lặp; để làm được việc này ta cần phải tìm hiểu về bản chất của mảng \(T\). Theo định nghĩa, mảng được tạo để: nếu một phép so khớp bắt đầu ở vị trí \(S[m]\) thất bại khi so sánh \(S[m\) + \(i]\) với \(W[i]\), thì phép so khớp có thể thành công tiếp theo sẽ bắt đầu ở vị trí\( S[m + (i – T[i])]\). Cụ thể hơn, phép so khớp tiếp theo sẽ bắt đầu tại vị trí có chỉ số cao hơn m, vì vậy \(T[i]\) < \(i\).

Từ điều này, chúng ta thấy rằng vòng lặp có thể thực hiện 2k lần. Với mỗi lần lặp, nó thực hiện một trong hai nhánh của vòng lặp. Nhánh thứ nhất tăng i và không thay đổi m, vì vậy chỉ số m + i của ký tự đang so sánh trên S tăng lên. Nhánh thứ hai cộng thêm i – T[i] vào m, và như chúng ta đã biết, đây luôn là số dương. Vì vậy, vị trí m, vị trí bắt đầu của một phép so khớp tiềm năng tăng lên. Vòng lặp dừng nếu m + i = k; vì vậy mỗi nhánh của vòng lặp có thể được sử dụng trong tối đa k lần, do chúng lần lượt tăng giá trị của m + i hoặc m, và m ≤ m + i: nếu m = k, thì m + i ≥ k, vì vậy: do các phép toán chủ yếu tăng theo đơn vị, chúng ta đã có m + i = k vào một thời điểm nào đó trước, và vì vậy thuật toán dừng.

Do đó vòng lặp chủ yếu thực hiện \(2k\) lần, độ phức tạp tính toán của thuật toán tìm kiếm chỉ là \(O(k)\).

Mã giả của thuật toán tạo bảng KMP

algorithm kmp_table:
    input:
        mảng ký tự, W 
        mảng số nguyên, T 
    output:
        mảng T

    define variables:
        biến kiểu nguyên, pos ← 2 
        biến kiểu nguyên, cnd ← 0  
    let T[0] ← -1, T[1] ← 0 
    while pos nhỏ hơn độ dài của W, ‘’’do’’’:
        (trường hợp một: tiếp tục dãy con)
        if W[pos - 1] = W[cnd], 
          let T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1

        (trường hợp hai: không thỏa mãn, nhưng ta có thể quay ngược trở lại)
        otherwise, if cnd > 0, let cnd ← T[cnd]

        (trường hợp ba: hết phần tử. Chú ý rằng cnd = 0)
        otherwise, let T[pos] ← 0, pos ← pos + 1

Độ phức tạp của thuật toán tạo bảng KMP

Độ phức tạp của thuật toán tạo bảng là \(O(n)\), với \(n\) là độ dài của \(W\). Ngoại trừ một số sắp xếp ban đầu, toàn bộ công việc được thực hiện trong vòng lặp \(while\), độ phức tạp của toàn bộ vòng lặp là \(O(n)\), với việc cùng lúc xử lý giá trị của pos và pos – cnd. Trong trường hợp thứ nhất, pos – cnd không thay đổi, khi cả \(pos\) và \(cnd\) cùng tăng lên một đơn vị. Ở trường hợp hai, \(cnd\) được thay thế bởi \(T[cnd]\), như chúng ta đã biết ở trên, luôn luôn nhỏ hơn \(cnd\), do đó tăng giá trị của pos – cnd. Trong trường hợp thứ ba, \(pos\) tăng và \(cnd\) thì không, nên cả giá trị của pos và pos – cnd đều tăng. Mà pos ≥ pos – cnd, điều này có nghĩa là ở mỗi bước hoặc \(pos\) hoặc chặn dưới \(pos\) đều tăng; mà thuật toán kết thúc khi \(pos=n\), nên nó phải kết thúc tối đa sau \(2n\) vòng lặp, do \(pos-cnd\) bắt đầu với giá trị 1. Vì vậy độ phức tạp của thuật toán xây dựng bảng là \(O(n)\).

Độ phức tạp của thuật toán KMP

Độ phức tạp của thuật toán là O(n)

Code trên C++

# #include 
#include 
#include 

using namespace std;

// Hàm tạo bảng LPS (Longest Prefix Suffix)
vector computePrefixFunction(const string& pattern) {
    int m = pattern.length();
    vector lps(m, 0); // Khởi tạo bảng LPS với kích thước m và giá trị ban đầu là 0
    int len = 0; // Chiều dài của prefix hiện tại
    int i = 1; // Bắt đầu từ ký tự thứ hai của pattern

    // Duyệt qua tất cả các ký tự của pattern
    while (i < m) {
        // Nếu ký tự hiện tại khớp với ký tự tại vị trí len
        if (pattern[i] == pattern[len]) {
            len++; // Tăng chiều dài prefix
            lps[i] = len; // Cập nhật giá trị LPS tại vị trí i
            i++; // Di chuyển sang ký tự tiếp theo
        } else {
            // Nếu không khớp
            if (len != 0) {
                len = lps[len - 1]; // Quay lại để kiểm tra prefix trước đó
            } else {
                lps[i] = 0; // Không có prefix nào
                i++; // Di chuyển sang ký tự tiếp theo
            }
        }
    }
    return lps; // Trả về bảng LPS
}

// Hàm tìm kiếm chuỗi con bằng thuật toán KMP
void KMPsearch(const string& text, const string& pattern) {
    int n = text.length(); // Chiều dài của chuỗi chính
    int m = pattern.length(); // Chiều dài của chuỗi con
    vector lps = computePrefixFunction(pattern); // Tạo bảng LPS cho pattern

    int i = 0; // Chỉ số cho chuỗi chính
    int j = 0; // Chỉ số cho chuỗi con

    // Duyệt qua chuỗi chính
    while (i < n) {
        // Nếu ký tự hiện tại của chuỗi chính khớp với ký tự của chuỗi con
        if (pattern[j] == text[i]) {
            i++; // Di chuyển sang ký tự tiếp theo trong chuỗi chính
            j++; // Di chuyển sang ký tự tiếp theo trong chuỗi con
        }

        // Nếu j đạt đến chiều dài của chuỗi con, nghĩa là tìm thấy chuỗi con
        if (j == m) {
            cout << "Pattern found at index " << (i - j) << endl; // In ra vị trí tìm thấy
            j = lps[j - 1]; // Cập nhật j để tiếp tục tìm kiếm
        } else if (i < n && pattern[j] != text[i]) { // Nếu gặp ký tự không khớp
            // Nếu j không bằng 0, quay lại theo bảng LPS
            if (j != 0) {
                j = lps[j - 1]; // Quay lại vị trí trong pattern theo bảng LPS
            } else {
                i++; // Nếu j bằng 0, chỉ cần di chuyển sang ký tự tiếp theo trong chuỗi chính
            }
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB"; // Chuỗi chính
    string pattern = "ABABCABAB"; // Chuỗi con cần tìm
    KMPsearch(text, pattern); // Gọi hàm tìm kiếm
    return 0;
}