如何找到最长回文子？

问题描述

下面是算法的书（由瓦齐拉尼）问题（6.7 CH6 ）的稍微不同于经典问题了finding最长的回文。我该如何解决这个问题呢？

解决方案

这可以在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 ?

解决方案

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.

---

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