এই সমস্যায়, আমাদের দুটি স্ট্রিং একটি পাঠ্য এবং একটি প্যাটার্ন দেওয়া হয়েছে। আমাদের কাজ হল প্যাটার্ন অনুসন্ধানের জন্য রাবিন-কার্প অ্যালগরিদমের জন্য একটি প্রোগ্রাম তৈরি করা, এটি টেক্সট স্ট্রিং-এ প্যাটার্নের সমস্ত ঘটনা খুঁজে পাবে।
এখানে, আমাদের টেক্সটে প্যাটার্নের সমস্ত ঘটনা খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
text = “xyztrwqxyzfg” pattern = “xyz”
আউটপুট
Found at index 0 Found at index 7
এখানে, আমরা Rabin-Karp অ্যালগরিদম ব্যবহার করে সমস্যার সমাধান নিয়ে আলোচনা করব। এই অ্যালগরিদমে, আমরা স্ট্রিং-এ প্যাটার্নের আকারের একটি উইন্ডো নিই এবং একে একে একে স্লাইড করি এবং প্যাটার্নের হ্যাশ মানের সাথে ম্যাচ করি। এবং যদি হ্যাশ-মান মিলে যায় তবে আমরা পরীক্ষা করব প্যাটার্নের পৃথক অক্ষরগুলি স্ট্রিংয়ের সাথে মেলে কিনা৷
রবিন-কার্পের জন্য টেক্সট এবং প্যাটার্নের হ্যাশ-মান গুরুত্বপূর্ণ, প্যাটার্ন তৈরির জন্য আমরা প্রত্যেকটির জন্য অক্ষরের সংখ্যাসূচক মান যোগ করব
স্ট্রিং এবং হ্যাশের অক্ষর বিবেচনা করা হবে মানটিকে ছোট করতে একটি মৌলিক সংখ্যা দিয়ে ভাগ করে।
প্যাটার্ন অনুসন্ধানের জন্য রাবিন-কার্প অ্যালগরিদমের জন্য প্রোগ্রাম
// প্যাটার্ন অনুসন্ধানের জন্য রাবিন-কার্প অ্যালগরিদমের জন্য প্রোগ্রাম
উদাহরণ
#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
