文字列Xとその文字列の逆であるYが与えられます。 XとYの最も長い共通シーケンスは常に回文であるか？

Question

私たちの教授は、私たちに次のような問題を与えた：

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." 

しかし、私はこの的アルゴリズムを実行し続けます（途中で私のものではない）、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の最も長い共通サブシーケンスが回文であるかどうかを証明するか、それとも反証することができますか？

Answer 1

X = 0,1,2,0,1の場合、 Y = reverse(X) = 1,0,2,1,0があり、最も長いサブシーケンスの1つは 0,2,1です。だからあなたの提案は一般的に成り立たない。しかし、問題に与えられたアルゴリズムによって返されたLCSは常に回文である可能性があります。私の例では、すべてのLCSの体系的列挙は、次のようになります： 0,1,0, 0,2,1,, 1,2,0, 1,2,1, 1,0,1 - 最初のLCSは本当に回文です。しかし、私はまだ一般的に証明することができませんでした。実際には両方とも（教授とあなた）正しいと思います：回文ではない Xと reverse(X)のLCSがあるかもしれませんが、LCSアルゴリズムのほとんどの（実際はまっすぐな）実装では、常に Xの回文が返されますおよび reverse(X)。