Chương trình C thuật toán KMP tìm mẫu trong chuỗi

Trong bài toán này, chúng ta được cho hai chuỗi: một chuỗi văn bản (text) và một chuỗi mẫu (pattern). Nhiệm vụ là viết chương trình thuật toán KMP để tìm kiếm mẫu, tìm tất cả các lần xuất hiện của mẫu trong chuỗi văn bản.

Chúng ta cần tìm tất cả các vị trí xuất hiện của mẫu trong văn bản.

Ví dụ minh họa bài toán

Đầu vào

text = "xyztrwqxyzfg" pattern = "xyz"

Đầu ra

Found at index 0 Found at index 7

Giải pháp sử dụng thuật toán KMP (Knuth Morris Pratt) tìm kiếm mẫu, sử dụng tiền xử lý chuỗi mẫu để tạo mảng tiền tố-hậu tố (prefix-suffix array) giúp bỏ qua các so sánh không cần thiết khi gặp ký tự không khớp.

Chúng ta tiền xử lý mẫu để tạo mảng chứa độ dài tiền tố dài nhất cũng là hậu tố (proper prefix and suffix) giúp tìm vị trí mismatch.

Chương trình thuật toán KMP tìm mẫu

// Chương trình C thuật toán KMP tìm mẫu

Ví dụ

#include 
#include 
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
    int length = 0;
    pps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[length]) {
            length++;
            pps[i] = length;
            i++;
        } else {
            if (length != 0)
                length = pps[length - 1];
            else {
                pps[i] = 0;
                i++;
            }
        }
    }
}
void KMPAlgorithm(char* text, char* pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int pps[M];
    prefixSuffixArray(pattern, M, pps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == M) {
            printf("Found pattern at index %d\n", i - j);
            j = pps[j - 1];
        }
        else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = pps[j - 1];
            else
                i = i + 1;
        }
    }
}
int main() {
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    KMPAlgorithm(text, pattern);
    return 0;
}

Kết quả

The pattern is found in the text at the following index -

Found pattern at index 0
Found pattern at index 7