Task 3 (66 points) Generate all palindromic decompositions of a string s (cut it

Question

Task 3 (66 points) Generate all palindromic decompositions of a string s (cut it into substrings that are palindromes). For example the string abbccd has 4 palindromic decompositions: a, b, b, c, c, d, a, b, b, cc, d, a, bb, c, c, d, a, bb, cc, d, Requirements: l. n m ain (or anolher un lionial will be called in main. repealedly read a string rom the user, unlil the user enler For each ofthese sin pnnl the palindrome decomposition (one per line, and a er that the total number of decompositions. 2. The function that generates the decompositions and counts them must be recursive . The maximum string length is 100 4. In the answers.pdf write the recurrence formula (Tn)- .. and the base case T

Explanation / Answer

#include<bits/stdc++.h>
using namespace std;

//Function to check if string is palindrome or not
bool isPalindrome(string strData, int first, int last)
{
//first is for starting index position and last is the last index position
//Loops till first is less than last
while (first < last)
{
//Checks if first index position character is not equals to last index position character
if (strData[first] != strData[last])
//Return false not palindrome
return false;
//Otherwise increase first by one to move to next character
first++;
//Decrease the last by one to move to one position before current position character
last--;
}//End of while
//Returns true for palindrome
return true;
}//End of function

// Recursively calls the function to find all palindromic partitions of string strData[startPos..endPos-1]
// allPart --> A vector of vector of strings. Every vector inside it stores a partition
// currentPart --> A vector of strings to store current partition
void allPalPartUtility(vector<vector<string> >&allPart, vector<string> &currentPart, int startPos, int endPos, string strData)
{
// If 'startPos' has reached length
if (startPos >= endPos)
{
allPart.push_back(currentPart);
return;
}//End of if

// Pick all possible ending points for substrings
for (int co = startPos; co < endPos; co++)
{
//Calls the function isPalindrome() to check if substring strData[startPos..co] is palindrome
if (isPalindrome(strData, startPos, co))
{
// Add the substring to result
currentPart.push_back(strData.substr(startPos, co - startPos + 1));

// Recur for remaining remaining substring
allPalPartUtility(allPart, currentPart, co + 1, endPos, strData);

// Remove substring strData[startPos..co] from current partition
currentPart.pop_back();
}//End of if
}//End of for
}//End of function

// Function to print all possible palindromic partitions of strData. It mainly creates vectors and calls allPalPartUtil()
void allPalPartitions(string strData)
{
int no = strData.length();
int ro, co;
// To Store all palindromic partitions
vector<vector<string> > allPart;

// To store current palindromic partition
vector<string> currentPart;

//Calls recursively allPalPartUtillity() function to generate all partitions and store in allPart
allPalPartUtility(allPart, currentPart, 0, no, strData);

// Print all partitions generated by above call
cout<<" Palindromic decomposition of string: ";
for (ro = 0; ro < allPart.size(); ro++ )
{
for (co = 0; co < allPart[ro].size(); co++)
cout << allPart[ro][co] << ", ";
cout << " ";
}//End of for loop
cout<<" The string "<<strData<<" has "<<ro<<" palindromic decompositions";
}//End of function

// main function definition
int main()
{
string stringData;
//Accepts a string from the user
cout<<" Enter a string to generate palindromic decomposition: ";
cin>>stringData;
//Calls the function allPalPartitions() to calculate number of palindromic decomposition and displays it
allPalPartitions(stringData);
return 0;
}//End of main function

Sample Run 1:

Enter a string to generate palindromic decomposition: abbccd

Palindromic decomposition of string:
a, b, b, c, c, d,
a, b, b, cc, d,
a, bb, c, c, d,
a, bb, cc, d,

The string abbccd has 4 palindromic decompositions

Samplr Run 2:

Enter a string to generate palindromic decomposition: thisis

Palindromic decomposition of string:
t, h, i, s, i, s,
t, h, i, sis,
t, h, isi, s,

The string thisis has 3 palindromic decompositions

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.