打印最长公共子序列

Question

我所面临的最长的问题是:对于Ex：

“ABCDGH” and “AEDFHR” is “ADH” of length 3

代码：

void lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

我不明白为什么这一行代码：

L[i][j] = max(L[i-1][j], L[i][j-1]);

如果我想打印序列，也就是ADH，我该怎么做呢？

Answer 1

我不明白为什么这一行代码： Li = max(Li-1，Li)；

如果X[0..i-1]的最后一个字符与Y[0..j-1]的最后一个字符不匹配，那么对于每个公共子序列，这些字符中至少有一个不属于。因此，给出的答案是X[0..i-2]和Y[0..j-1]的最大长度，或X[0..i-1]和Y[0..j-2]的最大长度。

为了恢复实际的子序列，我们必须像这样追溯这些决定。

char lcs[min(m, n) + 1];
char *end = lcs;
int i = m;
int j = n;
while (i > 0 && j > 0) {
    if (X[i - 1] == Y[j - 1]) {
        *end = X[i - 1];
        end++;
        i--;
        j--;
    } else if (L[i - 1][j] >= L[i][j - 1]) {
        i--;
    } else {
        j--;
    }
}
reverse(lcs, end);
*end = '\0';
puts(lcs);