給定一個字符串X和該字符串的反轉Y. X和Y最長的常見序列是迴文序列嗎？

我們的教授給了我們以下問題：給定一個字符串X和該字符串的反轉Y. X和Y最長的常見序列是迴文序列嗎？

Input 
    A sequence of characters X = x1, x2, ... ,xn 
Output 
    The length of the longest sub-sequence of X that is a palindrome

我的解決辦法是：

Take X and reverse it into the sequence Y = y1, y2, ... , yn 
Then perform LongestCommonSubsequence(X,Y)

他給了我部分信貸和中寫道，

"The LCS of X and reverse X is not necessarily a palindrome."

，但我一直運行此algorithim （不是我的，順便說一句），用X和X反轉，我得到的全是迴文。

/** 
** Java Program to implement Longest Common Subsequence Algorithm 
**/ 

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.io.IOException; 

/** Class LongestCommonSubsequence **/ 
public class LongestCommonSubsequence 
{  
/** function lcs **/ 
public String lcs(String str1, String str2) 
{ 
    int l1 = str1.length(); 
    int l2 = str2.length(); 

    int[][] arr = new int[l1 + 1][l2 + 1]; 

    for (int i = l1 - 1; i >= 0; i--) 
    { 
     for (int j = l2 - 1; j >= 0; j--) 
     { 
      if (str1.charAt(i) == str2.charAt(j)) 
       arr[i][j] = arr[i + 1][j + 1] + 1; 
      else 
       arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]); 
     } 
    } 

    int i = 0, j = 0; 
    StringBuffer sb = new StringBuffer(); 
    while (i < l1 && j < l2) 
    { 
     if (str1.charAt(i) == str2.charAt(j)) 
     { 
      sb.append(str1.charAt(i)); 
      i++; 
      j++; 
     } 
     else if (arr[i + 1][j] >= arr[i][j + 1]) 
      i++; 
     else 
      j++; 
    } 
    return sb.toString(); 
} 
}

我該如何證明或反駁X和反向X的最長公共子序列是否是迴文？

來源

2016-12-03 Marco Lugo

此鏈接可能有所幫助：http://wcipeg.com/wiki/Longest_palindromic_subsequence 擾流板：LCS不一定輸出**迴文。 –

@coproc我認爲Tymur的鏈接確實提供了一個反例，請點擊這裏http://wcipeg.com/wiki/Longest_palindromic_subsequence#LCS-based_approach –

@גלעדברקן好的，對。我仍然認爲OP的LCS算法總是會返回一個迴文（另請參閱我的答案）。 – coproc

對於X = 0,1,2,0,1我們有Y = reverse(X) = 1,0,2,1,0和最長的子序列之一是0,2,1。所以你的主張不一般。但問題中給出的算法返回的LCS仍然可能是迴文。在我的例子中，所有LCS-s的系統枚舉如下所示：0,1,0,0,2,1,0,2,0,1,2,0,1,2,1,1,0,1 - 並且第一個LCS確實是一個迴文。但是我一般還不能證明。所以我認爲實際上（教授和你）都是對的：雖然可以有一個不是迴文的X和的LCS，但是LCS算法的大多數（實際上是直截了當的）實現將總是返回一個迴文X和reverse(X)。（完全證明仍然丟失）

來源

2016-12-03 21:48:32 coproc

給定一個字符串X和該字符串的反轉Y. X和Y最長的常見序列是迴文序列嗎？

回答

相關問題