ইনপুট হিসাবে আমাদের একটি স্ট্রিং str[] দেওয়া হয়েছে। লক্ষ্য হল str[]-এ উপস্থিত অ্যানাগ্রাম সাবস্ট্রিংয়ের সংখ্যা গণনা করা। দুটি স্ট্রিং একে অপরের অ্যানাগ্রাম হয় যদি তাদের মধ্যে একই সংখ্যক অক্ষর থাকে এবং সমস্ত অক্ষর উভয়েই ঘটে। অক্ষরের ক্রম ভিন্ন হতে পারে।
“abc” হল “cba”, “bca” ইত্যাদির একটি অ্যানাগ্রাম।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str[] =“abccb”
আউটপুট − মোট অ্যানাগ্রাম সাবস্ট্রিংগুলির সংখ্যা হল − 4
ব্যাখ্যা − অ্যানাগ্রাম হল −(b,b), (c,c), (bc,cb), (bcc,ccb)
ইনপুট − str =“aaa”
আউটপুট − মোট অ্যানাগ্রাম সাবস্ট্রিংগুলির সংখ্যা হল − 4
ব্যাখ্যা − অ্যানাগ্রাম হল −(a,a), (a,a), (a,a), (aa,aa)
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা সাবস্ট্রিংয়ে ইংরেজি বর্ণমালার ফ্রিকোয়েন্সি সহ ভেক্টর সম্বলিত একটি মানচিত্র নিচ্ছি এবং অ্যারেতে এই জাতীয় সাবস্ট্রিংগুলির গণনা করছি। মানচিত্রে<ভেক্টর
-
স্ট্রিং str[] কে ক্যারেক্টার অ্যারে হিসেবে নিন।
-
ফাংশন anagram_substring(string str, int length) স্ট্রিং নেয় এবং মোট অ্যানাগ্রাম সাবস্ট্রিং এর গণনা প্রদান করে।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
একটি মানচিত্র নিন, মানচিত্র<ভেক্টর
, int> mp_vec; -
ট্রাভার্স str[] i=0 থেকে i
-
প্রতিটি সাবস্ট্রিং str[i থেকে j] এর জন্য। ভেক্টর
vec(MAX, 0); এতে ইংরেজি বর্ণমালার সংখ্যা থাকবে। -
str[j] হিসাবে c-এ বর্তমান অক্ষর নিন। 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
