ในปัญหานี้ เราได้รับข้อความและรูปแบบสองสตริง งานของเราคือสร้างโปรแกรมสำหรับอัลกอริทึม Rabin-Karp สำหรับการค้นหารูปแบบ โดยจะค้นหารูปแบบที่เกิดขึ้นทั้งหมดในสตริงข้อความ
ในที่นี้ เราต้องหารูปแบบที่เกิดขึ้นทั้งหมดในข้อความ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
text = “xyztrwqxyzfg” pattern = “xyz”
ผลลัพธ์
Found at index 0 Found at index 7
ในที่นี้ เราจะพูดถึงวิธีแก้ปัญหาโดยใช้อัลกอริธึม Rabin-Karp ในอัลกอริธึมนี้ เราจะใช้หน้าต่างของขนาดของรูปแบบในสตริงแล้วเลื่อนทีละรายการแล้วจับคู่กับค่าแฮชของรูปแบบ และหากค่าแฮชตรงกัน เราจะตรวจสอบว่าอักขระแต่ละตัวของรูปแบบตรงกับสตริงหรือไม่
สำหรับ Rabin-Karp ค่าแฮชของข้อความและรูปแบบมีความสำคัญ สำหรับการสร้างรูปแบบ เราจะเพิ่มค่าตัวเลขของอักขระสำหรับทุก ๆ
อักขระของสตริงและแฮชจะถูกพิจารณาโดยการหารด้วยจำนวนเฉพาะเพื่อทำให้ค่ามีขนาดเล็ก
โปรแกรมสำหรับ Rabin-Karp Algorithm สำหรับการค้นหารูปแบบ
//โปรแกรมสำหรับ Rabin-Karp Algorithm สำหรับการค้นหารูปแบบ
ตัวอย่าง
#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;
} ผลลัพธ์
พบรูปแบบในข้อความที่ดัชนีต่อไปนี้ -
Pattern found at index 0 Pattern found at index 7
