हमें एक स्ट्रिंग str[] और एक वर्ण X दिया गया है। लक्ष्य str[] के सबस्ट्रिंग को इस प्रकार खोजना है कि सभी सबस्ट्रिंग में कम से कम एक बार X हो। str[]=”abc' और X='a' के लिए, कम से कम एक बार 'a' वाले सबस्ट्रिंग्स "a", "ab", "abc" हैं। गिनती 3 है।
आइए उदाहरणों से समझते हैं।
इनपुट − str[] ="aabccd" X='c'
आउटपुट − उप-स्ट्रिंग की संख्या जिनमें कम से कम एक बार वर्ण X होता है − 14
स्पष्टीकरण - कम से कम एक 'सी' वाले सबस्ट्रिंग होंगे:"सी", "सी", "बीसी", "सीसी", "सीडी", "एबीसी", "बीसीसी", "सीसीडी", "एएबीसी", " एबीसीसी", "बीसीसीडी", "एएबीसीसी", "एबीसीसीडी", "एएबीसीसीडी"।
इनपुट - str[] ="सेटिंग्स" X='s'
आउटपुट − उप-स्ट्रिंग की संख्या जिनमें कम से कम एक बार वर्ण X होता है − 14
स्पष्टीकरण - सबस्ट्रिंग में कम से कम एक 'एस' होगा:"एस", "एस", "से", "जीएस", "सेट", "एनजी", "सेट", "आईएनजी", "सेटी", " tings", "सेटिन", "टिंग्स", "सेटिंग", "सेटिंग", "सेटिंग्स"
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम जानते हैं कि n वर्णों के साथ स्ट्रिंग के सबस्ट्रिंग की कुल संख्या n*(n+1)/2 है।
अब हम स्ट्रिंग को पार करेंगे और वर्ण X से पहले वर्णों को अस्थायी के रूप में गिनेंगे। जैसे ही एक्स का सामना करना पड़ता है, एक्स युक्त स्ट्रिंग्स की लंबाई अस्थायी + 1 होगी। अब हमारे पास एक्स युक्त सबस्ट्रिंग्स की संख्या शेष वर्ण (लंबाई-वर्तमान सूचकांक) एक्स (अस्थायी + 1) होगी। इसे गिनने के लिए जोड़ें। अब अस्थायी =0 अपडेट करें और स्ट्रिंग के अंत तक अगले एक्स के लिए आगे बढ़ें। अंत में हमें उप-स्ट्रिंग की संख्या के रूप में गिना जाता है जिसमें कम से कम एक बार वर्ण X होता है।
-
एक स्ट्रिंग str और एक वर्ण x लें।
-
फ़ंक्शन sub_x(char str[],int length,char x) एक स्ट्रिंग लेता है, इसकी लंबाई, वर्ण x और उन सबस्ट्रिंग्स की गिनती देता है जिनमें कम से कम एक बार वर्ण x होता है।
-
प्रारंभिक गणना को 0 के रूप में लें। शुरुआत में str[] में पहले x से पहले अस्थायी को वर्णों के रूप में लें।
-
str[] के सभी संभावित सबस्ट्रिंग की संख्या के लिए प्रारंभिक गणना आकार*(आकार+1)/2 लें।
-
ट्रैवर्स str[] लूप के लिए i=0 से i<आकार तक का उपयोग कर रहा है।
-
यदि str[i] x नहीं है, तो पहले x से पहले वर्णों के रूप में अस्थायी वृद्धि करें।
-
अगर str[i] ==x तो x सहित स्ट्रिंग की लंबाई temp+1 होगी। str[] के शेष अक्षर लंबाई-i होंगे।
-
सभी सबस्ट्रिंग्स (temp+1) * (लंबाई-i) होंगी। इसे गिनने के लिए जोड़ें। अब अगले पुनरावृत्ति के लिए अस्थायी =0 अपडेट करें।
-
ऐसा तब तक करें जब तक कि str[] का अंत न हो जाए।
-
अंत में परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
int count = 0;
int temp = 0;
for (int i = 0; i < length; i++){
if (str[i] == x){
int temp_2 = temp + 1;
count = count + temp_2 * (length - i);
temp = 0;
}
else{
temp++;
}
}
return count;
}
int main(){
string str = "abcabbc";
int length = str.length();
char x = 'a';
cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of sub-strings that contain character X at least once are: 19