问题描述
下面是算法的书(由瓦齐拉尼)问题(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< = 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.
这篇关于如何找到最长回文子?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!