如何找到最长的回文子序列？

Question

这是来自Algorithms book(Vazirani)的问题(6.7 ch6),与发现最长回文的经典问题略有不同.我怎么解决这个问题 ？

如果从左到右或从右到左读取它是相同的,则子序列是回文.例如,序列

A,C,G,T,G,T,C,A,A,A,A,T,C,G

有许多回文子序列,包括A,C,G,C,A和A,A,A,A (另一方面,子序列 A,C,T不是回文).设计一个算法,该算法采用一个序列x[1 ...n]并返回(最长的)最长的回文子序列.它的运行时间应该是O(n^2)

Answer 1

这可以使用动态编程在O(n ^ 2)中求解.基本上,问题是在x[i...j]使用最长的子序列时构建最长的回文子序列x[i+1...j],x[i,...j-1]并且x[i+1,...,j-1](如果第一个和最后一个字母是相同的).

首先,空字符串和单个字符串通常是回文.请注意,对于子字符串x[i,...,j],如果x[i]==x[j],我们可以说最长的回文长度是最长的回文结构x[i+1,...,j-1]+2.如果它们不匹配,最长的回文最大值为x[i+1,...,j]和y[i,...,j-1].

这给了我们这个功能:

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

您可以简单地实现该函数的memoized版本,或者编写一个最长[i] [j]自下而上的表.

这只给出了最长子序列的长度,而不是实际的子序列本身.但它也可以很容易地扩展到这样做.

Answer 2

该问题也可以作为称为LCS(最长公共子序列)问题的非常常见问题的变体来完成.让输入字符串由字符数组s1 [0 ... n-1]表示.

1)反转给定的序列并将反向存储在另一个数组中,例如s2 [0..n-1],其本质上是s1 [n-1 .... 0]

2)给定序列s1和反向序列s2的LCS将是最长的回文序列.

该解决方案也是O(n ^ 2)解决方案.