如何找到最长的回文子序列(不是它的长度) [英] How to find the longest palindromic subsequence (not its length)

问题描述

我想找出字符串中最长的回文子序列.我到处都找到了找出子序列长度的算法，并声明算法也可以扩展以返回子序列，但我没有找到方法.谁能解释一下我怎样才能得到序列?

I want to find out the longest palindromic subsequence in a string. Everywhere I find the algorithm to find out the length of the subsequence, with the statement that the algo can be extended to return the subsequence as well, but nowhere have I found how. Can anybody explain how can I get the sequence as well?

推荐答案

既然你提到了链接 Longest Palindromic在 geeksforgeeks 中的子序列，我修改了解决方案以输出结果.我想我们需要一个辅助的二维数组来存储回文子序列的来源，这样我们最终可以通过辅助数组得到结果.您可以在以下代码中看到逻辑:

Since you mentioned the link Longest Palindromic Subsequence in geeksforgeeks, I modified the solution to output the result. I think we need one auxiliary two-dimensions array to stored how the palindromic subsequence comes from, so we can get the result through the auxiliary array at last. You can see the logic in the below code:

#include<iostream>
#include<cstring>

using namespace std;

// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq
int lps(char *str,char *result)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  // Create a table to store results of subproblems

   int Way[n][n];// Store how the palindrome come from.


   // Strings of length 1 are palindrome of lentgh 1
   for (i = 0; i < n; i++)
   {
       L[i][i] = 1;
       Way[i][i]=0;
   }


    // Build the table. Note that the lower diagonal values of table are
    // useless and not filled in the process. The values are filled in a
    // manner similar to Matrix Chain Multiplication DP solution (See
    // http://www.geeksforgeeks.org/archives/15553). cl is length of
    // substring
    for (cl=2; cl<=n; cl++)
    {
        for (i=0; i<n-cl+1; i++)
        {
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
            {
                   L[i][j] = 2;
                   Way[i][j]=0;     
            }

            else if (str[i] == str[j])
            {
                  L[i][j] = L[i+1][j-1] + 2;
                  Way[i][j]=0;
            }

            else
            {
                if(L[i][j-1]>L[i+1][j])
                {
                   L[i][j]=L[i][j-1];
                   Way[i][j]=1;                    
                }
                else
                {
                    L[i][j]=L[i+1][j];
                    Way[i][j]=2;  
                }

            }

        }
    }

    int index=0;
    int s=0,e=n-1;

    while(s<=e)
    {
         if(Way[s][e]==0)
         {
             result[index++]=str[s];
             s+=1;
             e-=1;

         }
         else if(Way[s][e]==1)e-=1;
         else if(Way[s][e]==2)s+=1;     
    }

    int endIndex=(L[0][n-1]%2)?index-1:index;

    for(int k=0;k<endIndex;++k)result[L[0][n-1]-1-k]=result[k];

    result[index+endIndex]='\0';


    return L[0][n-1];
}

/* Driver program to test above functions */
int main()
{
    char seq[] = "GEEKSFORGEEKS";
    char result[20];
    cout<<"The lnegth of the LPS is "<<lps(seq,result)<<":"<<endl;
    cout<<result<<endl;
    getchar();
    return 0;
}

希望有帮助！

以下是解释:

设 X[0..n-1] 是长度为 n 的输入序列，L(0, n-1) 是 X[0..n-1] 的最长回文子序列的长度.

Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic sub-sequence of X[0..n-1].

总共有 5 个案例.

1) 每一个字符都是一个长度为 1 的回文.对于给定序列中的所有索引 i，L(i, i) = 1.

1)Every single character is a palindrome of length 1. L(i, i) = 1 for all indexes i in given sequence.

2)只有2个字符，而且都是一样的.L(i, j) = 2.

2)There are only 2 characters and both are same. L(i, j) = 2.

3)有两个以上字符，且首尾字符相同L(i, j) = L(i + 1, j - 1) + 2

3)There are more than two characters, and first and last characters are the same L(i, j) = L(i + 1, j - 1) + 2

4)首尾字符不相同且L(i + 1, j)

4)First and last characters are not the same and L(i + 1, j)< L(i, j - 1). L(i, j) = L(i, j - 1).

5)首尾字符不一样，L(i + 1, j)>=L(i, j - 1).L(i, j) = L(i + 1, j).

5)First and last characters are not the same and L(i + 1, j)>=L(i, j - 1). L(i, j) = L(i + 1, j).

我们可以观察到，只有在情况 1,2 和 3 中，字符 X[i] 包含在最终结果中.我们用一个二维辅助数组来表示回文子序列是如何来的.案例 1、2、3 的值为 0；情况 4 的值为 1；案例 5 的值为 2.

We can observed that only in case 1,2 and 3, the character X[i] is included in the final result. We used a two-dimension auxiliary array to represent how the palindromic sub-sequence comes from. value 0 for case 1,2,3; value 1 for case 4; value 2 for case 5.

用辅助阵的方式.我们可以得到如下结果:

With the auxiliary array Way. We can get the result as below:

Let two variables s=0 and e=n-1.
While s<=e
Loop
    If Way[s][e]==0 Then X[s] should be included in the result and we store it in our result array.
    Else if Way[s][e]==1 Then X[s] should not be include in the result and update e=e-1 (because our result comes from case 4).
    Else if Way[s][e]==2 Then X[s] should not be include in the result and update s=s+1 (because our result comes from case 5).

当 s>e 时应该终止循环.这样我们就可以得到一半的结果，我们可以轻松地扩展它以获得整个结果.

The loop should be terminated when s>e. In that way we can get half part of the result and we can easily extend it to get the whole result.

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