如何找到最长的回文子序列(不是它的长度)

Question

我想找出一个字符串中最长的回文子序列.在任何地方我都找到算法来找出子序列的长度,并且声明可以扩展算法以返回子序列,但是我找不到如何.任何人都可以解释我怎样才能得到序列？

Answer 1

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

#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]的最长回文子序列的长度.

共有5例.

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

2)只有2个字符,两者都相同.L(i,j)= 2.

3)有两个以上的字符,第一个和最后一个字符是相同的L(i,j)= L(i + 1,j - 1)+ 2

4)第一个和最后一个字符不相同,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).

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

用辅助阵列Way.我们可以得到如下结果:

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时,应该终止循环.通过这种方式,我们可以获得结果的一半,我们可以轻松扩展它以获得整个结果.