আমরা একটি স্ট্রিং str দেওয়া হয়. লক্ষ্য হল str এর সাবস্ট্রিংগুলির সংখ্যা গণনা করা যার শুরু এবং শেষের অক্ষর একই। উদাহরণস্বরূপ, যদি ইনপুট হয় “baca” সাবস্ট্রিংগুলি হবে “b”, “a”, “c”, “a”, “aca”। মোট ৫.
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str="abaefgf"
আউটপুট −একই প্রথম এবং শেষ অক্ষর সহ সাবস্ট্রিংগুলির সংখ্যা হল:9
ব্যাখ্যা − সাবস্ট্রিং হবে
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
ইনপুট − str="abcdef"
আউটপুট −একই প্রথম এবং শেষ অক্ষর সহ সাবস্ট্রিংগুলির সংখ্যা হল:6
ব্যাখ্যা − সাবস্ট্রিং হবে −
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
প্রদত্ত সমস্যা সমাধানের জন্য একাধিক পন্থা হতে পারে যেমন নিষ্পাপ দৃষ্টিভঙ্গি এবং দক্ষ পদ্ধতি। সুতরাং আসুন প্রথমে নিষ্পাপ পদ্ধতির দিকে তাকাই। আমরা প্রতিটি দৈর্ঘ্যের সাবস্ট্রিংগুলিকে একটি ফাংশন চেক() এ পাস করব। যদি সেই সাবস্ট্রিং একই অক্ষর দিয়ে শুরু হয় এবং শেষ হয় তাহলে গণনা বৃদ্ধি করুন।
-
স্ট্রিং str নিন. str.size().
হিসাবে দৈর্ঘ্য গণনা করুন -
ফাংশন চেক (স্ট্রিং স্ট্র) সাবস্ট্রিং স্ট্র নেয় এবং এটি প্রথম এবং শেষ অক্ষর একই কিনা তা পরীক্ষা করে। ( str[0]==str[দৈর্ঘ্য-1])। সত্য হলে, 1 ফেরত দিন।
-
ফাংশন check_Start_End(string str, int length) str এবং এর দৈর্ঘ্য ইনপুট হিসাবে নেয় এবং str এর সাবস্ট্রিংগুলির গণনা প্রদান করে যা একই অক্ষর দিয়ে শুরু এবং শেষ হয়।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
লুপের জন্য দুই ব্যবহার করে ট্রাভার্স str। i=0 থেকে i<দৈর্ঘ্য এবং ভিতরের j=1 থেকে j=দৈর্ঘ্য-1।
-
আমরা সমস্ত দৈর্ঘ্যের substr(i,j) ব্যবহার করে সমস্ত সাবস্ট্রিং পাব। চেক করতে প্রতিটি সাবস্ট্রিং পাস করুন()। যদি এটি 1 রিটার্ন করে, তাহলে ইনক্রিমেন্ট কাউন্ট।
-
উভয়ের শেষে লুপ গণনাতে একই শুরু এবং শেষ অক্ষর সহ str এর অনেকগুলি সাবস্ট্রিং থাকবে৷
-
পছন্দসই ফলাফল হিসাবে রিটার্ন গণনা করুন।
দক্ষ পদ্ধতি
আমরা দেখতে পাচ্ছি, সেই উত্তরটি মূল স্ট্রিং-এর প্রতিটি অক্ষরের ফ্রিকোয়েন্সির উপর নির্ভর করে।
যেমন "bacba"-এ "b" এর ফ্রিকোয়েন্সি হল 2 এবং "b" সহ সাবস্ট্রিং হল "b", "bacb" এবং "b"।
যা 2+1C2=3। আমরা প্রথমে প্রতিটি অক্ষরের ফ্রিকোয়েন্সি পরীক্ষা করব এবং যোগ করব (char+1 এর ফ্রিকোয়েন্সি) C2 .
-
স্ট্রিং str নিন. str.size().
হিসাবে দৈর্ঘ্য গণনা করুন -
ফাংশন check_Start_End(string str, int length) str এবং এর দৈর্ঘ্য ইনপুট হিসাবে নেয় এবং str এর সাবস্ট্রিংগুলির গণনা প্রদান করে যা একই অক্ষর দিয়ে শুরু এবং শেষ হয়।
-
প্রারম্ভিক গণনা-০ নিন।
-
প্রতিটি অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করতে একটি অ্যারে অ্যারে[26] নিন।
-
ট্রাভার্স স্ট্রিং এবং স্টোর ফ্রিকোয়েন্সি arr[str[i]=’a’]++।
-
ট্রাভার্স ফ্রিকোয়েন্সি অ্যারে অ্যারে[26] এবং প্রতিটি ফ্রিকোয়েন্সির জন্য অ্যাআরআর[i] যোগ করুন arr[i]*(arr[i]+1)/2। গণনা করতে।
-
শেষ পর্যন্ত ফলাফল হিসাবে গণনা ফেরত.
উদাহরণ (নিষ্পাপ পদ্ধতি)
#include <bits/stdc++.h>
using namespace std;
int check(string str){
int length = str.length();
if(str[0] == str[length-1]){
return 1;
}
}
int check_Start_End(string str, int length){
int count = 0;
for (int i = 0; i < length; i++){
for (int j = 1; j <= length-i; j++){
if (check(str.substr(i, j))){
count++;
}
}
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of substrings with same first and last characters are: 13
উদাহরণ (দক্ষ পদ্ধতি)
#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
int count = 0;
int arr[maximum] = {0};
for(int i=0; i<length; i++){
arr[str[i] - 'a']++;
}
for (int i=0; i<maximum; i++){
count = count + (arr[i]*(arr[i]+1)/2);
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str,
length);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of substrings with same first and last characters are: 13
