如何找到最长回文子？ [英] how to find longest palindromic subsequence?

问题描述

下面是算法的书（由瓦齐拉尼）问题（6.7 CH6 ）的稍微不同于经典问题了<一href="http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string">finding最长的回文。我该如何解决这个问题呢？

  

一个序列是回文，如果它是   一样的，不管读从左到右或   从右到左。例如，该   序

  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 不是回文）。制定一个   算法，需要序列×[1-   ... N] 并返回（长度）   最长的回文序列。其   运行时间应为O（n ^ 2）

解决方案

这可以在O解决（N ^ 2）采用动态规划。基本上，这个问题是关于使用最长子序列的 X [i + 1的构建最长回文子在 X [我... J] 。 ..j] ， X [我，... J-1] 和 X [I + 1 ,. ..，J-1] （如果第一个和最后的字母是相同的）。

首先，空字符串和一个字符串是平凡的回文。 请注意，对于一个子 X [1，...，J] ，如果 X [I] == X [J] ，我们可以说，最长的回文的长度最长的回文超过 X [I + 1，...，J-1] +2 。如果它们不匹配，最长的回文是说的 X [I + 1，...，J] 和 Y [最大1，...，J-1] 。

这给我们的功能：

 最长的（I，J）= J-i + 1的，如果J-I＆LT; = 0，
              2 +最长第（i + 1，J-1）如果x [I] == X [j]的
              最大（最长第（i + 1，j）中，最长的（I，J-1）），否则
 

您可以简单地实现该功能的memoized版本，或最长的[I] [J]自下而上的。

的codeA表

这为您提供了最长的序列长度只有，而不是实际的序列本身。但它可以很容易地扩展到这样做也是如此。

---

Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ?

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

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

has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Devise an algorithm that takes a sequence x[1 ...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n^2)

解决方案

This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).

Firstly, the empty string and a single character string is trivially a palindrome. Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].

This gives us the function:

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

You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.

This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.

---

这篇关于如何找到最长回文子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！