algorithm - 3 个字符串的 LCS - 证明

Question

我们可以通过这种方式将下面文档中的两个字符串的 LCS 算法扩展到三个字符串吗？

http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf - 文档，第 5 页第 2 点。

1. 如果 xm != yn 或 xm != tj 那么 zk != xm 意味着 Z 是 Xm-1 和 Y 和 T 的 LCS。

“如果 zk != xm，则 Z 是 Xm−1 和 Y 和 T 的公共(public)子序列。如果存在 Xm − 1 和 Y 和 T 的公共(public)子序列 W，其长度大于 k，则 W 也将是是 X m 和 Y 和 T 的公共(public)子序列，与 Z 是 X 和 Y 和 T 的 LCS 的假设相矛盾。”

其中 T = 是我们的第三个字符串

Answer 1

思考这个问题的一个好方法是使用动态编程数组。对于 2 个字符串，如果字符串的长度为 M 和 N，则有一个大小为 M x N 的动态规划矩阵。对于 3 个字符串，如果字符串的长度为 L，则有一个大小为 L x M x N 的 3 维动态规划数组, M, N。在动态数组的每个条目 (i,j,k) 中，您将 LCS 的长度存储在长度为 i,j,k 的 3 个字符串的前缀之间。如果您知道条目 (i-1,j,k)、(i,j-1,k)、(i,j) 的解，就很容易看出如何计算数组中的条目 (i,j,k) ,k-1) 和 (i-1,j-1,k-1)。基本上，如果字符串中的位置 i、j 和 k 匹配，则前任 (i-1,j-1,k-1) 在传播到 (i,j,k) 之前将其条目递增 1，并且传播所有其他条目到 (i,j,k) 而不递增。然后你获取传播条目的最大值。这看起来像您的引述要说的，但是查看动态编程递归的一种简单方法是想象如果您知道所有上述前辈，您将如何计算数组中的 (i,j,k)。因此，您可以以 k 的递增顺序从索引 (1,1,k) 的第一列开始填充数组，然后以 j 的递增顺序(以 k 的递增顺序)填充 (1,j,k) ), 然后按 i 的递增顺序 (in increasing order of j) (in increasing order of k)) 填充 (i,j,k) 的数组。