algorithm - 将最长公共(public)子序列简化为最长递增子序列

Question

如果至多一个序列有重复，我们可以将最长公共(public)子序列问题简化为最长递增子序列问题。减少问题的过程说明here :

Suppose you have the sequences:

S1 = {D, B, A, C, E}
S2 = {E, Z, X, D, A, Y, C}

Then, create a sequence of integers S3, where you have to put the position of each element of S2 in S1 (if the element doesn't exists in S1, then ignore that element). In the example:

S3 = {4, 0, 2, 3}
// Z, X and Y in S2 where ignored

Then, just find the LIS in S3. To find the original elements, just use the integers in the LIS as indices of S1. For example, in this case the LIS of S3 is {0, 2, 3}, where that represents the sequence {D, A, C}.

这种方法如何运作？为什么这种归约解决了寻找最长公共(public)子序列的问题？

Answer 1

鉴于您构建 S3 的方式，您可以保证 S3 的元素“仅且全部”指向 S1 和 S2 的公共(public)元素。

通过使用位置并找到最长的递增子序列，您可以确保找到的是原始 S1 和 S2 的子序列，而不仅仅是它们共有的元素数量:

• 它将是S1的子序列，因为S3中元素的数值编码了S1中的位置，所以增加S3的子序列=S1的子序列
• 它将是 S2 的子序列，因为 S3 的元素中编码的元素与 S2 的元素的顺序相同，所以 S3 的子序列 = S2 的子序列

因此，S3的最长递增子序列将“编码”:

• S1 的子序列
• S2的子序列
• 一个只包含同时出现在 S1 和 S2 中的元素的序列
• 最长的此类子序列

即S1和S2的最长公共(public)子序列

您可以使用所描述的过程“解码”，即获取 S1 的元素，索引 = S3 的元素。

注意:正如链接中所指出的，这仅在最多有一个序列有重复时有效，并且在构建 S3 时，您应该将没有重复的序列作为 S1。

这似乎与更常见的 reduction of LIS to LCS 相反.