Thuật toán KMP (Knuth-Morris-Pratt)

Thuật toán KMP (Knuth-Morris-Pratt) là một thuật toán tìm kiếm chuỗi được sử dụng để tìm kiếm tất cả các vị trí của một chuỗi con trong một chuỗi lớn. Thuật toán KMP được đặt tên theo ba người tạo ra nó: Donald Knuth, Vaughan Pratt và James Morris. Thuật toán KMP giải quyết vấn đề tìm kiếm chuỗi một cách hiệu quả hơn so với thuật toán tìm kiếm chuỗi Brute Force (Vét cạn).

Thuật toán KMP (Knuth-Morris-Pratt)

Thuật toán KMP được đặt tên theo ba nhà toán học Donald Knuth, Vaughan Pratt và James Morris. Trong năm 1977, Knuth và Pratt đã công bố bài báo “Fast Pattern Matching in Strings” trong đó họ giới thiệu thuật toán KMP. Sau đó, Morris đã cải tiến thuật toán và công bố bài báo “Linear Pattern Matching Algorithms” vào năm 1977.

Trước khi thuật toán KMP được phát triển, phương pháp tìm kiếm chuỗi chính xác là Brute Force (Vét cạn), trong đó ta so sánh từng ký tự của chuỗi lớn với từng ký tự của chuỗi con. Tuy nhiên, Brute Force có thể rất chậm và không hiệu quả khi tìm kiếm chuỗi trong các chuỗi lớn.

Thuật toán KMP đã giải quyết vấn đề này bằng cách sử dụng bảng Prefix để xác định vị trí tiếp theo để tìm kiếm chuỗi con. Điều này giúp giảm số lần so sánh cần thiết và giúp thuật toán tìm kiếm chuỗi nhanh hơn.

Thuật toán KMP đã được sử dụng rộng rãi trong nhiều lĩnh vực, bao gồm công nghệ thông tin, khoa học dữ liệu, văn học kỹ thuật số và nhiều lĩnh vực khác. Nó là một phần quan trọng của các thư viện xử lý chuỗi phổ biến như String Matching Library của C++.

Các bước thực hiện Thuật toán KMP

Thuật toán KMP hoạt động bằng cách sử dụng một bảng tiền xử lý được gọi là bảng Prefix. Bảng Prefix được tính toán cho chuỗi con mà chúng ta muốn tìm kiếm. Sau khi tính toán xong, ta sử dụng bảng Prefix này để xác định vị trí tiếp theo để tìm kiếm chuỗi con.

Cụ thể, thuật toán KMP hoạt động như sau:

Bước 1. Tính toán bảng Prefix cho chuỗi con cần tìm kiếm.

Bước 2. Duyệt qua chuỗi lớn và so sánh từng ký tự của chuỗi lớn với từng ký tự của chuỗi con.

Bước 3. Nếu ký tự của chuỗi lớn và chuỗi con khớp nhau, ta tiếp tục so sánh tiếp theo.

Bước 4. Nếu ký tự của chuỗi lớn và chuỗi con không khớp nhau, ta sử dụng bảng Prefix để xác định vị trí tiếp theo để tìm kiếm chuỗi con.

Lặp lại bước 3 và 4 cho đến khi tìm thấy tất cả các vị trí của chuỗi con trong chuỗi lớn.

Ví dụ về Thuật toán KMP

Để minh họa cách thuật toán KMP hoạt động, chúng ta hãy xem xét một ví dụ đơn giản.

Giả sử chúng ta có chuỗi chính X = “ABCABAB” và chuỗi con cần tìm kiếm là Y = “ABAB”. Chúng ta sẽ sử dụng thuật toán KMP để tìm kiếm vị trí của chuỗi con Y trong chuỗi chính X.

Bước 1: Tạo bảng Prefix Đầu tiên, chúng ta tạo bảng Prefix cho chuỗi con Y như sau:

k Y[0:k] Prefix
0 A 0
1 AB 0
2 ABA 1
3 ABAB 2

Ở đây, k là chỉ số của ký tự cuối cùng trong Y[0:k], Prefix là giá trị độ dài của tiền tố lớn nhất của chuỗi con Y mà là cả hậu tố của Y[0:k].

Bước 2: Tìm kiếm chuỗi con Sau đó, chúng ta duyệt qua chuỗi chính X từ trái sang phải để tìm kiếm chuỗi con Y. Ban đầu, ta so sánh Y[0] với X[0] và thấy chúng giống nhau, sau đó ta so sánh Y[1] với X[1] và thấy chúng cũng giống nhau. Tuy nhiên, khi so sánh Y[2] với X[2], chúng ta thấy chúng không giống nhau.

Vì vậy, chúng ta sử dụng bảng Prefix để tìm kiếm vị trí tiếp theo để so sánh. Vị trí tiếp theo cần so sánh là 2, bởi vì tiền tố lớn nhất của Y[0:2] cũng là hậu tố của Y[0:3]. Do đó, chúng ta so sánh Y[2] với X[2], và thấy chúng vẫn không giống nhau.

Tiếp theo, chúng ta sử dụng bảng Prefix để tìm kiếm vị trí tiếp theo để so sánh. Vị trí tiếp theo cần so sánh là 1, bởi vì tiền tố lớn nhất của Y[0:1] cũng là hậu tố của Y[0:3]. Do đó, chúng ta so sánh Y[1] với X[3], và thấy chúng vẫn không giống nhau.

Tiếp tục sử dụng bảng Prefix, vị trí tiếp theo cần so sánh là 0, bởi vì tiền tố lớn nhất của Y[0:0] cũng là hậu tố của Y[0:3]. Do đó, chúng ta so sánh Y[0] với X[4], và thấy chúng giống nhau.

Sau đó, chúng ta tiếp tục so sánh Y[1] với X[5], Y[2] với X[6] và Y[3] với X[7]. Và chúng ta tìm thấy chuỗi con Y trong chuỗi chính X tại vị trí 3.

Vì vậy, kết quả của việc tìm kiếm chuỗi con Y trong chuỗi chính X là 3.

Cài đặt thuật toán với Python

def KMP(text, pattern):
    """
    Hàm KMP dùng để tìm kiếm chuỗi pattern trong chuỗi text.
    """
    n = len(text)
    m = len(pattern)

    # Tạo bảng Prefix
    prefix = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[j] != pattern[i]:
            j = prefix[j - 1]
        if pattern[j] == pattern[i]:
            j += 1
        prefix[i] = j

    # Duyệt qua chuỗi text và tìm kiếm chuỗi pattern
    j = 0
    for i in range(n):
        while j > 0 and pattern[j] != text[i]:
            j = prefix[j - 1]
        if pattern[j] == text[i]:
            j += 1
        if j == m:
            return i - m + 1

    return -1
text = "ABCABAB"
pattern = "ABAB"

# Tìm kiếm chuỗi pattern trong chuỗi text
index = KMP(text, pattern)

# In ra kết quả
if index != -1:
    print("Chuỗi pattern được tìm thấy trong chuỗi text tại vị trí: ", index)
else:
    print("Chuỗi pattern không được tìm thấy trong chuỗi text.")

Cài đặt thuật toán KMP với C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int KMP(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();

    // Tạo bảng Prefix
    vector<int> prefix(m);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[j] != pattern[i]) {
            j = prefix[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            j++;
        }
        prefix[i] = j;
    }

    // Duyệt qua chuỗi text và tìm kiếm chuỗi pattern
    j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && pattern[j] != text[i]) {
            j = prefix[j - 1];
        }
        if (pattern[j] == text[i]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }

    return -1;
}

int main() {
    string text = "ABCABAB";
    string pattern = "ABAB";

    // Tìm kiếm chuỗi pattern trong chuỗi text
    int index = KMP(text, pattern);

    // In ra kết quả
    if (index != -1) {
        cout << "Chuoi pattern duoc tim thay trong chuoi text tai vi tri: " << index << endl;
    } else {
        cout << "Chuoi pattern khong duoc tim thay trong chuoi text." << endl;
    }

    return 0;
}

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

Độ phức tạp của thuật toán KMP là O(n+m), trong đó n là độ dài của chuỗi văn bản và m là độ dài của chuỗi mẫu cần tìm. Thuật toán này có thể tìm kiếm chuỗi mẫu trong chuỗi văn bản với hiệu suất tốt hơn so với các thuật toán tìm kiếm chuỗi khác, đặc biệt là đối với các chuỗi có độ dài lớn.

Để hiểu rõ hơn về độ phức tạp của thuật toán KMP, chúng ta có thể phân tích từng phần của thuật toán. Đầu tiên, bước tạo bảng prefix có độ phức tạp O(m), với m là độ dài của chuỗi mẫu. Tiếp theo, bước duyệt qua chuỗi văn bản cũng có độ phức tạp O(n), với n là độ dài của chuỗi văn bản. Trong quá trình duyệt, mỗi ký tự trong chuỗi văn bản chỉ được so sánh tối đa một lần với các ký tự trong chuỗi mẫu, do đó số lần so sánh tối đa là O(n). Do đó, độ phức tạp của thuật toán KMP là O(n+m).

Vì vậy, thuật toán KMP là một thuật toán có hiệu suất tốt trong việc tìm kiếm chuỗi mẫu trong chuỗi văn bản.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *