এই সমস্যা, আমরা একটি স্ট্রিং দেওয়া হয়. এবং Q প্রশ্নগুলির প্রতিটিতে দুটি পূর্ণসংখ্যা l এবং r এবং অক্ষর ch আছে। আমাদের কাজ হল C++ এ সাবস্ট্রিং-এ অক্ষরের ফ্রিকোয়েন্সিগুলির জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা :এখানে প্রতিটি প্রশ্নের জন্য, আমরা str[l...r] সাবস্ট্রিং-এ 'ch' অক্ষরের সংঘটনের ফ্রিকোয়েন্সি খুঁজে পাব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
str = “tutorialspoint” Q = 2 0 6 t 5 13 i
আউটপুট
2 2
ব্যাখ্যা
ক্যোয়ারী 1 এর জন্য − সাবস্ট্রিংটি হল "টিউটোরিয়া", অক্ষরটি 2 বার প্রদর্শিত হয়৷
৷কোয়েরি 2 এর জন্য − সাবস্ট্রিং হল "ialspoint", অক্ষর i 2 বার প্রদর্শিত হয়
সমাধান পদ্ধতি
সমস্যা সমাধানের সহজ এবং সোজা পথ হল প্রতিটি কোয়েরির জন্য l থেকে r পর্যন্ত স্ট্রিং ট্র্যাভার্স করা এবং স্ট্রিংটিতে হ্যারাক্টার ch এর উপস্থিতি গণনা করা।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Query{
int l, r;
char ch;
};
int CalcCharFreq(string str, Query queries){
int count = 0;
for(int i = queries.l; i < queries.r; i++){
if(str[i] == queries.ch )
count++;
}
return count;
}
int main(){
string str = "tutorialspoint";
int Q = 2;
Query queries[Q];
queries[0].l = 0;
queries[0].r = 5;
queries[0].ch = 't';
queries[1].l = 5;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "<<CalcCharFreq(str, queries[i])<<"\n";
return 0;
} আউটপুট
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
অন্য পদ্ধতি প্রি-কম্পিউটেড অ্যারে ব্যবহার করে সমস্যাটি সমাধান করা হয়। এখানে, আমরা একটি 2D অ্যারে তৈরি করব যা সেই নির্দিষ্ট সূচক পর্যন্ত অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করবে অর্থাৎ freq[3][2] অক্ষরের ফ্রিকোয়েন্সি 'c' সূচক 2 এ সংরক্ষণ করবে। প্রাথমিকভাবে, সমস্ত ফ্রিকোয়েন্সি 0।
তারপরে, আমরা প্রতিটি সূচক মানতে অক্ষরের ফ্রিকোয়েন্সি প্রাক-গণনা করব। এর পরে, আমরা সূচী l-এ সংঘটনের ফ্রিকোয়েন্সি বিয়োগ করে রেঞ্জে অক্ষরের ফ্রিকোয়েন্সি খুঁজে পাব যেটি সূচক r থেকে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int charFreq[100][26];
struct Query{
int l, r;
char ch;
};
void countCharFreq(string str, int size){
memset(charFreq, 0, sizeof(int));
for (int i = 0; i < size; i++){
charFreq[i][str[i] - 'a']++;
}
for (int i = 1; i < size; i++) {
for (int j = 0; j < 26; j++)
charFreq[i][j] += charFreq[i - 1][j] ;
}
}
int CalcCharFreq(Query queries){
return charFreq[queries.r][queries.ch - 'a'] - charFreq[queries.l][queries.ch - 'a'];
}
int main(){
string str = "tutorialspoint";
int size = str.length();
int Q = 2;
countCharFreq(str, size);
Query queries[Q];
queries[0].l = 1;
queries[0].r = 13;
queries[0].ch = 't';
queries[1].l = 4;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is " <<CalcCharFreq( queries[i])<<"\n";
return 0;
} আউটপুট
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
