এই সমস্যায়, আমাদের একটি প্যালিনড্রোমিক স্ট্রিং দেওয়া হয়েছে। এবং আমাদের এই স্ট্রিং এর সমস্ত পার্টিশন প্রিন্ট করতে হবে। এই সমস্যায়, আমরা স্ট্রিংয়ের সম্ভাব্য সমস্ত প্যালিন্ড্রোম পার্টিশনগুলি কেটে এটি খুঁজে পাব৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
ইনপুট৷ − স্ট্রিং ='আবাবা'
আউটপুট − আবাবা , a bab a , a b a b a ….
এই সমস্যার সমাধান হল, একটি সাবস্ট্রিং প্যালিনড্রোম কিনা তা পরীক্ষা করা। এবং সাবস্ট্রিং প্রিন্ট করুন যদি এটি সাবস্ট্রিং হয়।
উদাহরণ
নিচের প্রোগ্রামটি সমাধানটি ব্যাখ্যা করবে −
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
while (low < high) {
if (str[low] != str[high])
return false;
low++;
high--;
}
return true;
}
void palindromePartition(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str){
if (start >= n) {
allPart.push_back(currPart);
return;
}
for (int i=start; i<n; i++){
if (isPalindrome(str, start, i)) {
currPart.push_back(str.substr(start, i-start+1));
palindromePartition(allPart, currPart, i+1, n, str);
currPart.pop_back();
}
}
}
void generatePalindromePartitions(string str){
int n = str.length();
vector<vector<string> > partitions;
vector<string> currPart;
palindromePartition(partitions, currPart, 0, n, str);
for (int i=0; i< partitions.size(); i++ ) {
for (int j=0; j<partitions[i].size(); j++)
cout<<partitions[i][j]<<" ";
cout<<endl;
}
}
int main() {
string str = "abaaba";
cout<<"Palindromic partitions are :\n";
generatePalindromePartitions(str);
return 0;
} আউটপুট
Palindromic partitions are : a b a a b a a b a aba a b aa b a a baab a aba a b a aba aba abaaba
