আমরা একটি স্ট্রিং str দেওয়া হয়. লক্ষ্য হল str এর সমস্ত সাবস্ট্রিং গণনা করা যেগুলি বিশেষ প্যালিন্ড্রোম এবং দৈর্ঘ্য 1 এর বেশি। বিশেষ প্যালিন্ড্রোমগুলি হল স্ট্রিং যেগুলির হয় একই অক্ষর রয়েছে বা শুধুমাত্র মধ্যম অক্ষরটি ভিন্ন। উদাহরণস্বরূপ, যদি স্ট্রিং হয় "baabaa" তাহলে বিশেষ প্যালিন্ড্রোমগুলি হল মূলের সাবস্ট্রিং হল "aa", "aabaa", "aba", "aa"
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − str="abccdcdf"
আউটপুট − একটি স্ট্রিং-এ বিশেষ প্যালিনড্রোমের সংখ্যা হল −3
ব্যাখ্যা − বিশেষ প্যালিনড্রোমগুলির সাবস্ট্রিংগুলি হল − “cc”, “cdc”, “dcd”
ইনপুট − str="baabaab"
আউটপুট − একটি স্ট্রিং-এ বিশেষ প্যালিনড্রোমের সংখ্যা হল −4
ব্যাখ্যা − সাবস্ট্রিংগুলি যেগুলি বিশেষ প্যালিনড্রোমগুলি হল − “aa”, “aabaa”, “aba”, “aa”
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
-
বর্ণমালার একটি স্ট্রিং তৈরি করুন এবং এর দৈর্ঘ্য গণনা করুন। আরও প্রক্রিয়াকরণের জন্য ফাংশনে ডেটা পাস করুন।
-
একটি অস্থায়ী ভেরিয়েবল গণনা এবং i ঘোষণা করুন এবং তাদের সেট করুন 0
-
একটি স্ট্রিংয়ের আকারের একটি অ্যারে তৈরি করুন এবং এটি 0 দিয়ে শুরু করুন।
-
শুরু করুন যতক্ষণ না আমি একটি স্ট্রিংয়ের দৈর্ঘ্যের চেয়ে কম হয়
-
সময়ের ভিতরে, একটি ভেরিয়েবলকে মোট 1 এবং একটি ভেরিয়েবল j কে i + 1
-
আরেকটি শুরু করুন যতক্ষণ না str[i] =str[j] এবং j একটি স্ট্রিংয়ের দৈর্ঘ্যের চেয়ে কম
-
সময়ের ভিতরে, মোট 1 দ্বারা এবং 1 দ্বারা j বৃদ্ধি করুন
-
গণনাটিকে গণনা হিসাবে সেট করুন + ( মোট * (মোট + 1) / 2, arr[i] মোট এবং i-তে j
-
স্টার্ট লুপ ফর j থেকে 1 পর্যন্ত একটি স্ট্রিং এর দৈর্ঘ্য পর্যন্ত
-
str[j] =str[j-1] কিনা চেক করুন তারপর arr[j] এ arr[j-1] সেট করুন
-
একটি ভেরিয়েবল টেম্প str[j-1] সেট করুন এবং j> 0 এবং j <একটি স্ট্রিং এর দৈর্ঘ্য কম কিনা তা পরীক্ষা করুন AND temp =str[j+1] AND sr[j]!=temp তারপর গণনা হিসাবে গণনা সেট করুন + min(arr[j-1], arr[j+1])
-
গণনা একটি গণনা সেট করুন - একটি স্ট্রিংয়ের দৈর্ঘ্য
-
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len){
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len){
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++){
if (str[j] == str[j - 1]){
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main(){
string str = "bcbaba";
int len = str.length();
cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of special palindromes in a String are: 3
