我目前正在尝试查找和打印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];
}
}
}
似乎没有简单的方法可以完成,因为如果仅保留最后两列,则必不可少的信息就会丢失。
例如,考虑两种情况:(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。
同时,还有一个更高级的算法可以在二次时间和线性空间中工作。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句