Need help to answer this question Reference book \"introduction to algorithms 3r
ID: 3670455 • Letter: N
Question
Need help to answer this question Reference book "introduction to algorithms 3rd edition pdf" Chapter 15 google the book to get it as pdf you will need the book.
Qn 3 (10 points) (Problem 15-2 of CLRS3 on page 405.) Longest palindrome subse- quence A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar and aibohphobia (fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a subsequence of Give an efficient algorithm to find the longest palindrome that is a a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm?Explanation / Answer
//Dynamic Programming based Python program for LPS problem
//Returns the length of the longest palindromic subsequence in seq
#include<stdio.h>
#include<string.h>
// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
int lps(char *str)
{
int n = strlen(str);
int i, j, cl;
int L[n][n]; // Create a table to store results of subproblems
// Strings of length 1 are palindrome of lentgh 1
for (i = 0; i < n; i++)
L[i][i] = 1;
// Build the table. Note that the lower diagonal values of table are
// useless and not filled in the process. The values are filled in a
// manner similar to Matrix Chain Multiplication DP solution (See
// http://www.geeksforgeeks.org/archives/15553). cl is length of
// substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKS FOR GEEKS";
int n = strlen(seq);
printf ("The lnegth of the LPS is %d", lps(seq));
getchar();
return 0;
}
//You can easily modift to get string. Just go through code and understand