c++ - 打印最长公共(public)子序列

Question

我在最长子序列中面临的问题: 例如:

“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

I don't understand why this line of code:

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

如果 X[0..i-1] 的最后一个字符与 Y[0..j-1] 的最后一个字符不匹配，那么对于每个公共(public)子序列，至少有一个不属于这些字符。因此，答案由 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);