এই সমস্যায়, আমাদের দুটি স্ট্রিং দেওয়া হয়েছে একটি টেক্সট সাইজ n এবং অন্য একটি প্যাটার্ন সাইজ m। আমাদের কাজ হল অ্যানাগ্রাম সাবস্ট্রিং অনুসন্ধানের জন্য একটি প্রোগ্রাম তৈরি করা।
এখানে, আমাদের পাঠ্যটিতে প্যাটার্নের সমস্ত উপস্থিতি এবং এর সমস্ত স্থানান্তর (অ্যানাগ্রাম) খুঁজে বের করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
text = “xyztrwqyzxfg” pattern = “xyz”
আউটপুট
Found at index 0 Found at index 7
এই সমস্যাটি সমাধান করার জন্য, আমাদের রবিন কার্প অ্যালগরিদম এর অনুরূপ একটি অ্যালগরিদম ব্যবহার করতে হবে যেটি একটি সংখ্যার মডিউলের অধীনে সমস্ত অক্ষরের ASCII মান যোগ করে অ্যানাগ্রাম ঘটনা পরীক্ষা করতে ব্যবহৃত হয়। এবং তারপর বৈশিষ্ট্যগুলির একটি উইন্ডো ব্যবহার করে এবং যোগফলের সাথে মিলে যায়।
সমাধানটির জন্য দুটি অ্যারের প্রয়োজন হবে যা পাঠ্যের উইন্ডোতে অক্ষরের ফ্রিকোয়েন্সি এবং সাথে মিলিত প্যাটার্ন সংরক্ষণ করতে হবে। তারপরে আমরা উইন্ডোটিকে একটি করে স্লাইড করব এবং প্রতিটি বিধবার জন্য অক্ষর ফ্রিকোয়েন্সি এবং ম্যাচিং প্যাটার্নের মুদ্রণের সাথে মিল করব৷
অ্যানাগ্রাম সাবস্ট্রিং অনুসন্ধানের জন্য প্রোগ্রাম
//অ্যানাগ্রাম সাবস্ট্রিং অনুসন্ধানের জন্য প্রোগ্রাম
উদাহরণ
#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
bool matchPattern(char arr1[], char arr2[]){
for (int i = 0; i < MAX; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
void anagramSearch(char* pattern, char* text){
int M = strlen(pattern);
int N = strlen(text);
char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
for (int i = 0; i < M; i++) {
(patternArray[pattern[i]])++;
(textArray[text[i]])++;
}
for (int i = M; i < N; i++) {
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value : %d", (i-M));
(textArray[text[i]])++;
textArray[text[i - M]]--;
}
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value: %d", (N-M));
}
int main() {
char text[] = "xyztrwqyzxfg";
char pattern[] = "xyz";
printf("Searching Anagram pattern in the string ");
anagramSearch(pattern, text);
return 0;
} আউটপুট
Searching Anagram pattern in the string Pattern found at index value: 0 Pattern found at index value: 7
