हमें इनपुट के रूप में एक स्ट्रिंग str[] दी गई है। लक्ष्य str[] में मौजूद एनाग्राम सबस्ट्रिंग की संख्या को गिनना है। दो तार एक दूसरे के विपर्यय होते हैं यदि उनमें समान संख्या में वर्ण हों और सभी वर्ण दोनों में हों। वर्णों का क्रम भिन्न हो सकता है।
"abc" "cba", "bca" आदि का विपर्यय है।
आइए उदाहरणों से समझते हैं।
इनपुट - str[] ="abccb"
आउटपुट − कुल विपर्यय सबस्ट्रिंग की संख्या है − 4
स्पष्टीकरण - विपर्यय हैं - (बी, बी), (सी, सी), (बीसी, सीबी), (बीसीसी, सीसीबी)
इनपुट - str ="आआ"
आउटपुट − कुल विपर्यय सबस्ट्रिंग की संख्या है − 4
स्पष्टीकरण - विपर्यय हैं - (a,a), (a,a), (a,a), (aa,aa)
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
हम एरे में ऐसे सबस्ट्रिंग्स की सबस्ट्रिंग और गिनती में अंग्रेजी अक्षरों की आवृत्तियों के साथ वेक्टर युक्त नक्शा ले रहे हैं। मानचित्र में<वेक्टर
-
स्ट्रिंग str[] को एक वर्ण सरणी के रूप में लें।
-
फंक्शन anagram_substring(string str, int length) स्ट्रिंग लेता है और कुल एनाग्राम सबस्ट्रिंग की गिनती देता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
नक्शा लें, नक्शा<वेक्टर
, int> mp_vec; -
ट्रैवर्स str[] i=0 से i<लंबाई और j=i से j<लंबाई तक दो for लूप का उपयोग करते हुए।
-
प्रत्येक सबस्ट्रिंग के लिए str [i से j]। वेक्टर
vec(MAX, 0); इसमें अंग्रेजी अक्षरों की संख्या होगी। -
सी में वर्तमान चरित्र को स्ट्र [जे] के रूप में लें। इसका पूर्णांक मान temp=c-'a' से लें।
-
vec[temp]++ द्वारा आवृत्ति अपडेट करें।
-
mp_vec[vec]++ का उपयोग करके इस आवृत्ति वेक्टर के अनुरूप गिनती बढ़ाएं।
-
अब ट्रैवर्स मैप जिसमें सभी फ़्रीक्वेंसी वेक्टर और एग्रीगेट सबस्ट्रिंग काउंट का उपयोग करके इटरेटर से लूप के लिए उपयोग किया जाता है it=mp_vec.begin() !=mp_vec.end()।
-
प्रत्येक गणना के लिए->दूसरा, जोड़ें ((अंतिम) * (अंतिम -1))/2 विपर्यय के सभी जोड़े के लिए गिनने के लिए
-
अंत में हमारे पास सभी विपर्ययणों की गिनती होगी।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int anagram_substring(string str, int length){
int count = 0;
map<vector<int>, int> mp_vec;
for (int i=0; i<length; i++){
vector<int> vec(MAX, 0);
for (int j=i; j<length; j++){
char c = str[j];
char temp = c - 'a';
vec[temp]++;
mp_vec[vec]++;
}
}
for (auto it = mp_vec.begin(); it != mp_vec.end(); it++){
int last = it->second;
count += ((last) * (last-1))/2;
}
return count;
}
int main(){
string str = "TP";
int length = str.length();
cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of total anagram substrings are: 3