通过动态程序查找最长的子字符串

Question

回文是一个与其反向相同的字符串。以下字符串是回文的示例：abba、refer、0101010、x。字符串X = x1, x2, x3, . . . , xn的子字符串是这样Y = y1, y2, . . . , yk y1 = xi1 , y2 = xi2 , . . . , yk = xik and i1 < i2 < . . . ik 的字符串。

例如，2， 7， 4

是 1， 2， 8， 7， 4 的子字符串。设计最有效的动态规划算法，该算法可以输入长度为 n 的字符串 X 并查找 X 的最长子字符串（回文）的长度。这个问题可以在O（n^2）时间内解决吗？

Answer 1

这是

子字符串的情况。但是您在问题中的示例指示了一个子序列。O（n^2） 解决方案将是这样的 -len（l，r）- x[l..r].

for i=1 to n
 for j=1 to n
  if(i=j) 
    len(i,j)=1       //1-length palindromes
  if(i+1=j)
     then len(i,j)=2 if (x[l]=x[r]),or 1 otherwise //for even-length palindrome. 
  if(x[l]=x[r]) 
     then len(i,j)=2+len(i+1,j-1) //both character same
  else
     len(l,r)=maximum(len(l,r-1),len(l+1,r)); //increase left,decrease right

答案是len（1，n），它将在O（n^2）时间内找到。