এই সমস্যাতে, আমাদের দুটি স্ট্রিং দেওয়া আছে: একটি টেক্সট এবং একটি প্যাটার্ন। আমাদের কাজ হল রাবিন-কার্প অ্যালগরিদম ব্যবহার করে প্যাটার্ন সার্চের প্রোগ্রাম তৈরি করা, যা টেক্সট স্ট্রিং-এ প্যাটার্নের সকল আওয়ারেন্স খুঁজে বের করবে।
এখানে, আমাদের টেক্সট-এ প্যাটার্নের সকল আওয়ারেন্স খুঁজে বের করতে হবে।
সমস্যা বোঝার জন্য একটি উদাহরণ নিই,
ইনপুট
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
