LCS算法中子序列的确定

Question

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

当我们也感兴趣寻找最长的子序列本身(而不仅仅是它的长度)时，我们创建一个辅助性(字符串1长度X字符串2长度)矩阵，通过将箭头、左箭头或对角线箭头相加来确定子序列是什么，对应于我们来自何处，这样以后我们就可以追溯我们的步骤并找到子序列本身。

(参见这里的示例:最后一页的http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf )

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

- 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

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

Answer 1

当使用简单的动态编程方法(如上面所示)时，您只能用最后一列来确定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算法的分治自适应算法，在线性空间中工作.

欲进一步阅读：f03/Artikler/05/Hirschberg75.pdf