5. (10 pts) A palindrome is any string that is exactly the same as its reversal,

Question

5. (10 pts) A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACANALPANAMA. For example, in sequence MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM, the longest subsequence that is a palindrome is MHYMRORMYHM, so given that string as input, your algorithm should output the number 11 (a) (7 pts) Describe in pseudo-code an O(n2) time algorithm to find the length of the longest subsequence of a given string that is also a palindrome. The key is to find a recursive description of the optimal solution in terms of the optimal solution of smaller subproblems. If you are unable to find an O(n2) time algorithm, then for part marks, you can give an O(n3) or O(n4 time algorithm. (b) (3 pts) Analyze the running time of your algorithm.

Explanation / Answer

Consider String to be tested as str.

n = str.length(); // get length of input string

// table[i][j] will be false if substring str[i..j] is not palindrome. Else table[i][j] will be true

boolean table[][] = new boolean[n][n];

maxLength = 1; // All substrings of length 1 are palindromes

FOR i = 0 To n

table[i][i] = true;

END FOR

start = 0;

FOR i = 0 TO n - 1 // check for sub-string of length 2.

  

IF str.charAt(i) = str.charAt(i + 1)

table[i][i + 1] = true;

start = i;

maxLength = 2;

END IF

  

END FOR

FOR K = 3 TO N // Check for lengths greater than 2. k is length of substring   

FOR i = 0 TO n - k   

int j = i + k - 1; // Get the ending index of substring from starting index i and length k

IF table[i + 1][j - 1] and str.charAt(i) = str.charAt(j) //checking for sub-string from ith index to jth index iff str.charAt(i+1) to str.charAt(j-1) is a palindrome

table[i][j] = true;

IF k > maxLength

start = i;

maxLength = k;

END IF

END IF

END FOR

END FOR

print maxLength; // print length of Longest Palindrome Substring.

(b) Since there is only one nested loop so complexity is O(n2).

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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