最长公共子序列优化

我目前正在尝试查找和打印2个给定字符串的最长公共子序列。我使用最常用的算法，无需递归。如果我保留整个数组，这很简单，但我想优化一下，只使用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]; 
     } 
    } 
}

来源

2015-04-22 Dcortez

[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem）这会帮助你。 –

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

例如，考虑两种情况：（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。

与此同时，有a more advanced algorith在二次时间和线性空间工作。

来源

2015-04-22 18:17:27 Petr

尽管我正在使用行，并且在您的示例“acc”和“bcc”中有不同的最后2行，但我知道有些情况下它们会相同。 Hitschberg算法会做，但我想我会留在整个桌子。感谢帮助！ – Dcortez

最长公共子序列优化

回答

相关问题