0

上周我一直在研究 LCS 问题，我有一个问题。

每当我们也对找到最长的子序列本身（而不仅仅是它的长度）感兴趣时，我们创建一个辅助 (string1.length X string2.length) 矩阵，通过添加向上箭头、向左箭头或对角箭头来确定子序列是什么，对应于我们来自哪里，因此我们可以稍后回溯我们的步骤并找到子序列本身。

（参见此处的示例：http: //www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf在最后一页）

我的问题是：考虑以下输出矩阵来运行这两个字符串：“abfcytyruc”和“vxczcxabfc”通过 LCS：

- 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 1 1 1 1
- 0 0 0 0 0 0 0 1 2 2 2
- 0 0 0 0 0 0 0 1 2 3 3
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 1 1 1 2 3 4
- 0 0 0 1 1 2 2 2 2 3 4

我们真的可以仅根据矩阵中的最后一列找到公共子序列，而不需要更多的空间复杂度吗？

4

1 回答 1

0

当使用简单的动态规划方法（如上）时，您只能确定最后一列的 LCS 的长度，而不是实际的序列。

这是一个失败的例子：

  a a a a a c b b
c 0 0 0 0 0 1 1 1
b 0 0 0 0 0 1 2 2
b 0 0 0 0 0 1 2 3
a 1 1 1 1 1 1 2 3
a 1 2 2 2 2 2 2 3
a 1 2 3 3 3 3 3 3
a 1 2 3 4 4 4 4 4

看看 Hirschberg 算法。它是对 Needleman-Wunsch 算法的分而治之的改编，在线性空间中工作。

进一步阅读：http ://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/05/Hirschberg75.pdf

于 2013-11-22T20:50:38.447 回答