Chương trình C thuật toán Rabin-Karp 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 Rabin-Karp để 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 Rabin-Karp: lấy một cửa sổ (window) có kích thước bằng mẫu trong chuỗi và trượt từng bước một, so sánh giá trị hash của cửa sổ với hash của mẫu. Nếu giá trị hash khớp, kiểm tra từng ký tự của mẫu có khớp với chuỗi hay không.

Đối với Rabin-Karp, giá trị hash của văn bản và mẫu rất quan trọng. Để tạo hash của mẫu, cộng giá trị số của từng ký tự trong chuỗi và lấy modulo một số nguyên tố để giá trị nhỏ lại.

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

// Chương trình thuật toán Rabin-Karp tìm mẫu

Ví dụ

#include 
#include 
#define c 256
void search(char pattern[], char text[]){
    int M = strlen(pattern);
    int N = strlen(text);
    int i, j;
    int hashP = 0;
    int hashT = 0;
    int h = 1;
    for (i = 0; i < M - 1; i++)
        h = (h * c) % 103;
    for (i = 0; i < M; i++) {
        hashP = (c * hashP + pattern[i]) % 103;
        hashT = (c * hashT + text[i]) % 103;
    }
    for (i = 0; i <= N - M; i++) {
        if (hashP == hashT) {
            for (j = 0; j < M; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == M)
                printf("Pattern found at index %d \n", i);
        }
        if (i < N - M) {
            hashT = (c * (hashT - text[i] * h) + text[i + M]) % 103;
            if (hashT < 0)
                hashT = (hashT + 103);
        }
    }
}
int main(){
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    search(pattern, text);
    return 0;
}

Kết quả

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

Pattern found at index 0
Pattern found at index 7