इस समस्या में हमें एक तार दिया जाता है। और Q प्रश्नों में से प्रत्येक में दो पूर्णांक l और r और वर्ण ch हैं। हमारा कार्य C++ में सबस्ट्रिंग में वर्णों की आवृत्तियों के प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण :यहां प्रत्येक क्वेरी के लिए, हम सबस्ट्रिंग str[l...r] में वर्ण 'ch' के घटित होने की आवृत्ति पाएंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
str = “tutorialspoint” Q = 2 0 6 t 5 13 i
आउटपुट
2 2
स्पष्टीकरण
क्वेरी 1 के लिए - विकल्प "ट्यूटोरिया" है, वर्ण t 2 बार प्रकट होता है।
क्वेरी 2 के लिए - सबस्ट्रिंग "ialspoint" है, वर्ण मैं 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