एनाग्राम पैटर्न सर्च

एनाग्राम मूल रूप से किसी दी गई स्ट्रिंग या पैटर्न के सभी क्रमपरिवर्तन हैं। यह पैटर्न सर्चिंग एल्गोरिदम थोड़ा अलग है। इस मामले में, न केवल सटीक पैटर्न खोजा जाता है, यह टेक्स्ट में दिए गए पैटर्न के सभी संभावित व्यवस्थाओं को खोजता है।

इस समस्या को हल करने के लिए, हम पूरे टेक्स्ट को पैटर्न के समान लंबाई की कई विंडोज़ में विभाजित करेंगे। फिर पैटर्न के प्रत्येक कैरेक्टर की काउंट मिलती है और एक ऐरे में स्टोर की जाती है। प्रत्येक विंडो के लिए, हम काउंट ऐरे ढूंढने का भी प्रयास करते हैं, फिर जांचते हैं कि वे मेल खा रहे हैं या नहीं।

एनाग्राम पैटर्न सर्च एल्गोरिदम की टाइम कॉम्प्लेक्सिटी O(n) है।

इनपुट और आउटपुट

इनपुट: मेन स्ट्रिंग "AABAACBABBCABAABBA"। पैटर्न "AABC"।
आउटपुट: एनाग्राम मिला स्थिति: 2
एनाग्राम मिला स्थिति: 3
एनाग्राम मिला स्थिति: 4
एनाग्राम मिला स्थिति: 10

एल्गोरिदम

anagramSearch(text, pattern)

इनपुट: मेन स्ट्रिंग और पैटर्न
आउटपुट: वे सभी लोकेशन जहां पैटर्न और इसके सभी एनाग्राम मिले।

Begin
    patternFreq ऐरे और stringFreq ऐरे परिभाषित करें
    patLen := pattern की लंबाई
    stringLen := टेक्स्ट की लंबाई
    patternFreq ऐरे की सभी एंट्रीज़ को 0 पर सेट करें
    for all characters present in pattern, do
        फ्रीक्वेंसी बढ़ाएं।
    done
    for i := 0 to i <= stringLen - patLen, do
        stringFreq की सभी एंट्रीज़ को 0 पर सेट करें
        for all characters of each window, do
            फ्रीक्वेंसी बढ़ाएं
        done
        if stringFreq और patternFreq समान हैं, then
            i का मान प्रदर्शित करें, क्योंकि उस लोकेशन पर एनाग्राम मिला
        done
    done
End

उदाहरण

#include <iostream>
#include <cstring>
#define LETTER 26
using namespace std;

bool arrayCompare(int *array1, int *array2, int n) {
    for(int i = 0; i < n; i++) {
        if(array1[i] != array2[i])
            return false; // यदि एक मिसमैच है तो काम रोक दें
    }
    return true; // ऐरे समान हैं
}

void setArray(int *array, int n, int value) {
    for(int i = 0; i < n; i++)
        array[i] = value; // ऐरे में सभी स्थानों के लिए वैल्यू रखें
}

void anagramSearch(string mainString, string patt, int *array, int *index) {
    int strFreq[LETTER], pattFreq[LETTER];
    int patLen = patt.size();
    int stringLen = mainString.size();
    setArray(pattFreq, LETTER, 0); // सभी फ्रीक्वेंसी को 0 से इनिशियलाइज़ करें
    for(int i = 0; i < patLen; i++) {
        int patIndex = patt[i] - 'A'; // A का ASCII घटाएं
        pattFreq[patIndex]++; // फ्रीक्वेंसी बढ़ाएं
    }
    for(int i = 0; i <= (stringLen - patLen); i++) {
        // वह रेंज जहां विंडो मूव करेगी
        setArray(strFreq, LETTER, 0); // मेन स्ट्रिंग के लिए सभी फ्रीक्वेंसी को 0 से इनिशियलाइज़ करें
        for(int j = i; j < (i + patLen); j++) { // प्रत्येक विंडो के लिए फ्रीक्वेंसी अपडेट करें।
            int strIndex = mainString[j] - 'A';
            strFreq[strIndex]++; // फ्रीक्वेंसी बढ़ाएं
        }
        if(arrayCompare(strFreq, pattFreq, LETTER)) { // जब दोनों ऐरे समान हों
            (*index)++;
            array[*index] = i; // एनाग्राम ith पोजीशन पर मिला
        }
    }
}

int main() {
    string mainStrng = "AABAACBABBCABAABBA";
    string pattern = "AABC";
    int matchLocation[mainStrng.size()];
    int index = -1;
    anagramSearch(mainStrng, pattern, matchLocation, &index);
    for(int i = 0; i <= index; i++) {
        cout << "Anagram found at position: " << matchLocation[i] << endl;
    }
}

आउटपुट

Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10