问寻找最长的公共差分子序列

EN

您可以通过将每个列表中的每个元素减去列表中最小的元素来转换您的问题。

例如，：

在A中，得到: min(A) =2，然后A= {0,2,4,10} 在B中，得到: min(B)=4，然后是B={0,4,10}

现在的问题是如何找到最长的公共子序列.

我想你可以在网上或任何地方找到解决这个问题所需要的东西：

维基百科关于最长子序列的文章

希望它能帮上忙

编辑

@Saeed Amiri是对的，我的回答是正确的当且仅当A和B的最小元素在最长的子序列中。

所以它给了我一个解决这个问题的新想法：

设D(i，j)是最长子序列的长度，使得它在A中的最小元素是A(排序)的第一个元素，它在B中的最小元素是B的jth元。

然后

D(i，j) =x{ A-A(i) }相交{ B (j) }

(符号：|A|=card(A))

你需要在i和j上找到D(i，j)的最大值，你知道

0<=D(i，j)<=min(\x{e76f}\x{e76f}

所以，如果你发现D(i，j) =min(\x，x，b，-i)，你就不需要测试i'，j‘，这样的话，你就不需要测试min(\x，b，-j’)<=m_1(_A_~_

它不是很有效(在最坏的情况下是O(n*m))，但至少它纠正了我的错误。

应该管用的，

希望它能帮上忙

如果推到紧要关头，你总是可以尝试把k添加到一个序列中的所有元素中，然后运行最长的公共子序列，对于所有可能的k值。

如果您计算每个序列中每个可能的值发生的频率，那么您可以在与每个k关联的最长公共子序列上放置一个上限，方法是计算所有相同字符排列的匹配数。这将允许您从k的最有希望的值开始，然后丢弃到目前为止无法超过最佳答案的k值，而不需要为它们计算最长的公共子序列。