আমাদের একটি স্ট্রিং str[] এবং একটি অক্ষর X দেওয়া হয়েছে। লক্ষ্য হল str[] এর সাবস্ট্রিংগুলি খুঁজে বের করা যাতে সমস্ত সাবস্ট্রিংয়ে অন্তত একবার X থাকে। str[]=”abc'' এবং X=’a’-এর জন্য, অন্তত একবার ‘a’ ধারণকারী সাবস্ট্রিংগুলি হল “a”, “ab”, “abc”। গণনা 3।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str[] =“aabccd” X=’c’
আউটপুট − অন্তত একবার X অক্ষর ধারণ করে এমন সাব-স্ট্রিংগুলির সংখ্যা হল − 14
ব্যাখ্যা − কমপক্ষে একটি 'c' ধারণকারী সাবস্ট্রিংগুলি হবে:"c", "c", "bc", "cc", "cd", "abc", "bcc", "ccd", "aabc", " abcc", "bccd", "aabcc", "abccd", "aabccd"।
ইনপুট − str[] =“সেটিংস” X=’s’
আউটপুট − অন্তত একবার X অক্ষর ধারণ করে এমন সাব-স্ট্রিংগুলির সংখ্যা হল − 14
ব্যাখ্যা − সাবস্ট্রিং-এ রয়েছে- অন্তত একটি 's' হবে:“s”, “s”, “se”, “gs”, “set”, “ngs”, “sett”, “ings”, “setti”, “ টিংস", "সেটিন", "টিংস", "সেটিং", "এটিংস", "সেটিংস"
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
এই পদ্ধতিতে আমরা জানি যে n অক্ষর সহ স্ট্রিং এর মোট সাবস্ট্রিং সংখ্যা হল n*(n+1)/2।
আমরা এখন স্ট্রিংটি অতিক্রম করব এবং টেম্প হিসাবে X অক্ষরের আগে অক্ষর গণনা করব। X সম্মুখীন হওয়ার সাথে সাথে, X সম্বলিত স্ট্রিংগুলির দৈর্ঘ্য টেম্প+1 থাকবে। এখন আমাদের কাছে X সংখ্যার সাবস্ট্রিং রয়েছে যার মধ্যে X থাকবে অবশিষ্ট অক্ষর (দৈর্ঘ্য-বর্তমান সূচক) X ( টেম্প+1)। গণনা করতে এই যোগ করুন. এখন temp=0 আপডেট করুন এবং স্ট্রিং শেষ না হওয়া পর্যন্ত পরবর্তী X-এর জন্য এগিয়ে যান। শেষে আমরা সাব-স্ট্রিংগুলির সংখ্যা হিসাবে গণনা করেছি যাতে অন্তত একবার X অক্ষর থাকে।
-
একটি স্ট্রিং স্ট্র এবং একটি অক্ষর x নিন।
-
ফাংশন sub_x(char str[],int length,char x) একটি স্ট্রিং নেয়, এটির দৈর্ঘ্য, অক্ষর x এবং অন্তত একবার x অক্ষর ধারণ করে এমন সাবস্ট্রিংগুলির গণনা প্রদান করে।
-
প্রারম্ভিক গণনাটিকে 0 হিসাবে নিন। প্রথমে str[]-এ 0 হিসাবে প্রথম x এর আগে অক্ষর হিসাবে temp নিন।
-
str[] এর সম্ভাব্য সকল সাবস্ট্রিং এর সংখ্যার জন্য প্রাথমিক গণনার আকার*(আকার+1)/2 নিন।
-
i=0 থেকে i
-
যদি str[i] x না হয় তাহলে প্রথম x এর আগে অক্ষর হিসাবে তাপমাত্রা বৃদ্ধি করুন।
-
যদি str[i] ==x হয় তাহলে x সহ স্ট্রিংয়ের দৈর্ঘ্য হবে temp+1। str[] এর অবশিষ্ট অক্ষর হবে দৈর্ঘ্য-i।
-
সমস্ত সাবস্ট্রিং হবে ( টেম্প+1) * (দৈর্ঘ্য-i)। গণনা করতে এই যোগ করুন. এখন পরবর্তী পুনরাবৃত্তির জন্য temp=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
