एनाग्राम सबस्ट्रिंग सर्च के लिए सी प्रोग्राम

इस समस्या में, हमें दो स्ट्रिंग एक टेक्स्ट आकार 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