Trong bài toán này, chúng ta có hai chuỗi một văn bản và một mẫu. Nhiệm vụ của chúng tôi là tạo một chương trình cho thuật toán Rabin-Karp để tìm kiếm mẫu, nó sẽ tìm tất cả các lần xuất hiện của mẫu trong chuỗi văn bản.
Ở đây, chúng ta phải tìm tất cả các lần xuất hiện của mẫu trong văn bản.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
text = “xyztrwqxyzfg” pattern = “xyz”
Đầu ra
Found at index 0 Found at index 7
Ở đây, chúng ta sẽ thảo luận về giải pháp của vấn đề bằng cách sử dụng thuật toán Rabin-Karp. Trong thuật toán này, chúng tôi lấy một cửa sổ có kích thước bằng kích thước của mẫu trong chuỗi và trượt lần lượt và đối sánh nó với giá trị băm của mẫu. Và nếu giá trị băm khớp thì chúng tôi sẽ kiểm tra xem các ký tự riêng lẻ của mẫu có khớp với chuỗi hay không.
Đối với Rabin-Karp, giá trị băm của văn bản và mẫu là quan trọng, để tạo mẫu, chúng tôi sẽ thêm giá trị số của ký tự cho mỗi
ký tự của chuỗi và hàm băm sẽ được xem xét bằng cách chia nó cho một số nguyên tố để tạo giá trị nhỏ.
Chương trình cho Thuật toán Rabin-Karp để Tìm kiếm Mẫu
// Chương trình cho Thuật toán Rabin-Karp để tìm kiếm mẫu
Ví dụ
#include <stdio.h>
#include <string.h>
#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;
} Đầu ra
Mẫu được tìm thấy trong văn bản tại chỉ mục sau -
Pattern found at index 0 Pattern found at index 7