最长公共子序列优化

Question

我目前正在为两个给定的字符串寻找和打印最长的公共子序列。我使用最常见的算法，没有递归。如果我保持整个数组，这是一个简单的任务，但是我尝试优化它，并且只使用2行，在下面的代码中可以看到这一点。通过这种改变，找到长度仍然很简单，工作也很好，但是恢复子序列已经不容易了。我试过用几种方式做这件事，但都没有用。下面你可以看到我最后一次尝试。虽然它适用于同样的情况，但也有失败的情况。经过很长一段时间的思考，我开始相信没有办法使用只有2行的数组来恢复子序列。我的研究并没有给出确切的答案，所以我在问是否有办法实现我想要做的事情？或者，如果我想打印的话，我会继续保持整个数组吗？

//finding length of longest common subsequence
for(int i=1; i<m; i++) {
    for(int j=1; j<n; j++) {
        if(sequece1[i-1] == sequence2[j-1]) {
            tab[i%2][j] = tab[(i-1)%2][j-1] + 1;
        } else {
            tab[i%2][j] = max(tab[i%2][j-1],tab[(i-1)%2][j]);
        }
    }
}

//trying to reconstruct longest common subsequence
int last_row = (m-1)%2;
for(int j=n-1; j>0; j--) {
    if(tab[last_row][j-1] < tab[last_row][j]) {
        if(last_row == 0) {
            common_part += sequence2[j];
            } else {
            common_part += sequence2[j-1];
        }
    }
}

Answer 1

似乎没有简单的方法可以完成，因为如果只保留最后两列，信息的一个重要部分就会丢失。

例如，考虑两种情况：(abcc，acc)字符串和(abcc，bcc)字符串。这些案例的矩阵将是

1 1 1 1    and  0 1 1 1
1 1 2 2         0 1 2 2
1 1 2 3         0 1 2 3

您将看到，最后两列在这两种情况下都是相同的，因此您将不会区分仅由最后两列判断的这些情况。但是您需要区分它们，因为答案是不同的(acc和bcc)。当然，您仍然有原始字符串，并且可以使用来自那里的信息，但是我认为(尽管我没有证明这一点)，这或多或少相当于为原始字符串的一些前缀查找LCS。

同时，存在在二次时间和线性空间中工作的一种更先进的藻类。