A string is called palindromic if it reads the same whether read left to right o
ID: 3671211 • Letter: A
Question
A string is called palindromic if it reads the same whether read left to right or right to left. Given a string S = s[1]s[2]...s[n], you want to find a longest subsequence of S that is palindromic. For example, if S = MAHATMA, then the longest subsequence of S that is palindromic is MAHAM.
Design an algorithm that outputs the length of the longest subsequence that is a palindrome for a given input string. Give pseudocode.
Design an algorithm that outputs a longest subsequence that is a palindrome for a given input string.
Explanation / Answer
Algorithm that outputs the length of the longest subsequence that is a palindrome for a given input string.
//The length procedure for finding length that will called on procedure palindromlength //
procedure length (F,x,i,j)
Input: Array F from procedure palindromlength;
Output: length of F[i,j]
if i = j:
return F[i,j]
else if x[i] = x[j]:
if i+1 < j-1:
return F[i+1,j-1] + 2
else:
return 2
else:
return max(F[i+1,j],F[i,j-1])
//main procedure palindromlength//
procedure palindromlength (s1,...,sn)
Input: Sequence( s1,...,sn)
Output: give the Length of the longest palindromic subsequence
F[i,j] are 2d array that stores the length of longest palindrome subsequence in (xi,...,xj)
for i = 1 to n:
F[i,i] = 1
for i = 1 to n:
for s = 1 to n-i:
j = s+i
F[s,j] = length (F,x,s,j)
F[j,s] = length (F,x,j,s)
return F[1,n]
Algorithm that outputs a longest subsequence that is a palindrome for a given input string.
//FOR THE LONGEST STRING //
procedure longestpalindrom(N,P1,P2)
Input: N IS THE STRING
Output: LONGEST STRING
if (P1 > P2)
return 0;
if (P1 == P2)
return 1;
if (N[P1] == N[P2])
return 2 + (N, P1+1, P2-1);
return max(N, P1+1, P2), (N, P1, P2-1));
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.