Question

a cheap solution is, let y be the reverse of x, and apply the standard longest common subsequence (lcs) algorithm to x and y. this approach is numerically correct, but flawed, since the character locations for a lcs in x and y does not have to reference the same sequence of physical characters. suppose x is zabza, what are the lcs for x and its reverse? how many are they? are they all palindrome?

Answer 1

Two LCSs for 'zabza' and its reverse 'azbaz' are 'zaz' and 'aba', both of which are palindromes as well as valid subsequences in the original string and its reverse.

Step-by-step explanation:

The question is asking about finding the longest common subsequence (LCS) between a string x and its reverse, y.

The example given is x being 'zabza' and its reverse, y, being 'azbaz'. When applying the standard LCS algorithm to x and y, the LCS could be 'zaz' or 'aba'.

There are two LCSs for this example, and yes, they are both palindromes, as a palindrome reads the same backward as forward.

The approach mentioned is numerically correct, but logically flawed. This is because finding the LCS of a string and its reverse does not guarantee that the LCS is a valid subsequence in the original string, as characters may not appear in the same order or position.

However, in this specific case of 'zabza', the LCSs 'zaz' and 'aba' do happen to be palindromes and subsequences in both the original string and its reverse.