Write a C code that generate all palindromic decompositions of a string s (cut i
ID: 3591193 • Letter: W
Question
Write a C code that generate all palindromic decompositions of a string s (cut it into substrings that are palindromes).
For example the string abbccd has 4 palindromic decompositions:
Requirements:
In main (or another function that will be called in main), repeatedly read a string from the user, until the user enters -1. For each of these strings, print the palindromic decomposition (one per line) and after that the total number of decompositions.
The function that generates the decompositions and counts them must be recursive.
The maximum string length is 100.
Explanation / Answer
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> ¤tPart, 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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.