将最长的公共子序列减少到最长的子序列 [英] Reducing Longest common subsequence to Longest increasing Subsequence

问题描述

如果最多一个序列具有重复，我们可以将最长公共子序列问题减少为最长增加子序列问题.在此处中说明了减少问题的过程:

假设您具有以下顺序:

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

然后，创建一个整数序列S3，您必须在其中将S2的每个元素的位置放在S1中(如果该元素在S1中不存在，则忽略该元素).在示例中:

  S3 = {4，0，2，3}//S2中的Z，X和Y被忽略 

然后，只需在S3中找到LIS.要查找原始元素，只需将LIS中的整数用作S1的索引.例如，在这种情况下，S3的LIS是 {0，2，3} ，其中代表序列 {D，A，C} .

这种方法如何起作用?为什么这种减少解决了找到最长的公共子序列的问题?

解决方案

鉴于如何构建S3，可以确保S3的元素指向仅且全部" S1和S2的共同元素.

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

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

因此，S3增长最快的子序列将编码":

• S1的子序列
• S2的子序列
• 仅包含S1和S2中都存在的元素的序列
• 此类子序列中最长的

即S1和S2之间最长的公共子序列

您可以使用上述过程解码"，即以index = S3的元素获取S1的元素.

注意:如链接中所指出的，仅在最多一个序列具有重复的情况下才有效，而构建S3时，您应将没有重复的序列作为S1.

这似乎是更常见的将LIS还原为LCS 的逆序./p>

We can reduce the Longest Common Subsequence problem to Longest Increasing Subsequence problem if at most one sequence has repetitions. The process of reducing the problem is explained 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}.

How does this approach work? Why does this reduction solve the problem of finding the longest common subsequence?

解决方案

Given how you build S3, you are guaranteed that the elements of S3 point to "only and all" the common elements of S1 and S2.

By using the positions and finding the longest increasing subsequence you make sure that what you find will be a subsequence of the original S1 and S2 and not just the number of elements they have in common:

• It will be a subsequence of S1 because the numerical value of the elements in S3 encode the positions in S1, so increasing subsequence of S3 = subsequence of S1
• It will be a subsequence of S2 because the elements encoded in the elements of S3 are in the same order as the elements of S2, so subsequence of S3 = subsequence of S2

Therefore, the longest increasing subsequence of S3 will "encode":

• a subsequence of S1
• a subsequence of S2
• a sequence that contains only elements present in both S1 and S2
• the longest of such subsequences

i.e. the longest common subsequence between S1 and S2

Which you can "decode" by using the process described, i.e. take the elements of S1 with index = element of S3.

NOTE: as pointed out in the link, this only works when at most one of the sequences has repetitions, and when building S3 you should take the sequence without repetitions as S1.

This seems like the inverse of the more common reduction of LIS to LCS.

这篇关于将最长的公共子序列减少到最长的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！