इस समस्या में, हमें दो स्ट्रिंग्स एक टेक्स्ट और एक पैटर्न दिया जाता है। हमारा काम पैटर्न खोज के लिए राबिन-कार्प एल्गोरिदम के लिए एक प्रोग्राम बनाना है, यह टेक्स्ट स्ट्रिंग में पैटर्न की सभी घटनाओं को ढूंढेगा।
यहां, हमें टेक्स्ट में पैटर्न की सभी घटनाओं का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
text = “xyztrwqxyzfg” pattern = “xyz”
आउटपुट
Found at index 0 Found at index 7
यहां, हम राबिन-कार्प एल्गोरिथम का उपयोग करके समस्या के समाधान पर चर्चा करेंगे। इस एल्गोरिथ्म में, हम स्ट्रिंग में पैटर्न के आकार की एक विंडो लेते हैं और इसे एक-एक करके स्लाइड करते हैं और इसे पैटर्न के हैश मान से मिलाते हैं। और अगर हैश-वैल्यू मैच होता है तो हम जांच करेंगे कि पैटर्न के अलग-अलग कैरेक्टर स्ट्रिंग के साथ मेल खाते हैं या नहीं।
राबिन-कार्प के लिए टेक्स्ट और पैटर्न का हैश-वैल्यू महत्वपूर्ण है, पैटर्न के निर्माण के लिए हम प्रत्येक के लिए कैरेक्टर का संख्यात्मक मान जोड़ेंगे
स्ट्रिंग और हैश के चरित्र को मान को छोटा करने के लिए इसे एक अभाज्य संख्या से विभाजित करके माना जाएगा।
पैटर्न खोज के लिए राबिन-कार्प एल्गोरिथम के लिए कार्यक्रम
// पैटर्न खोज के लिए राबिन-कार्प एल्गोरिथम के लिए कार्यक्रम
उदाहरण
#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