PLEASE THE PROGRAM SHOULD BE IN C LANGUAGE!!! NOT C++!! I REPEAT THE PROGRAM SHO

Question

PLEASE THE PROGRAM SHOULD BE IN C LANGUAGE!!! NOT C++!! I REPEAT THE PROGRAM SHOULD BE IN C LANGUAGE

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: 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.

write the recurrence formula (T(n) = .... and the base case T(...) = ... ) for the recursive function that generates the palindromes as a function of the string length, N

Explanation / Answer

Please find the code below:

// Function to print all distinct palindrome sub-strings of s

void palindromeSubStrs(string s)

{

map<string, int> m;

int n = s.length();

int R[2][n+1];

// We will now find all substring palindromes from the given input

// string insert 'guards' to iterate easily over s

s = "@" + s + "#";

for (int j = 0; j <= 1; j++)

{

int rp = 0;  

R[j][0] = 0;

int i = 1;

while (i <= n)

{

// Attempt to expand palindrome centered at i

while (s[i - rp - 1] == s[i + j + rp])

rp++;  

// Assigning the found palindromic length to odd/even

// length array

R[j][i] = rp;

int k = 1;

while ((R[j][i - k] != rp - k) && (k < rp))

{

R[j][i + k] = min(R[j][i - k],rp - k);

k++;

}

rp = max(rp - k,0);

i += k;

}

}

s = s.substr(1, n);

// We will put all obtained palindromes in a hash map to find only distinct palindromess

m[string(1, s[0])]=1;

for (int i = 1; i <= n; i++)

{

for (int j = 0; j <= 1; j++)

for (int rp = R[j][i]; rp > 0; rp--)

m[s.substr(i - rp - 1, 2 * rp + j)]=1;

m[string(1, s[i])]=1;

}

//printing all distinct palindromes from hash map

printf("Number of Palindrome subtrings: %d ",m.size()-1) ;

printf("Palindrome sub-strings as printed below: ");

map<string, int>::iterator i;

char* tmp;

for (i = m.begin(); i!=m.end(); ++i)

cout << i->first << endl;

}

int main()

{

char s[100];

while (1)

{

printf("Enter a string :");

scanf("%s",s);

if(strcmp(s,"-1")==0)

break;

palindromeSubStrs(s);

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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