给定不同长度的序列,找到每个序列共有的最大数字序列

Question

我有一个问题,我已经尝试了很多想法,但找不到最佳解决方案.

问题是这样的:

给定n个序列的序列全部按递增顺序排序但长度不同,找到每个序列共有的最大子序列.

例如,假设有3个序列A,B和C,

哪里

A = {1 3 5 7 9 10 11 15 30 43 44 45 50}
B = {1 2 3 7 8 10 11 12 23 27 30 38 40 41 45 50 51 53 }
C = {0 1 3 7 9 11 12 13 14 19 20 24 28 30  50 51 61 90 99}

因此,所有这些的最大公共子序列是:

Answer = {1 3 7 11 30 50}

上面的例子说明了我想传达的想法.我怎样才能找到这样一个最大的共同子序列？

感谢您花时间和考虑阅读这篇文章.如果你能提供建议,我将非常感激.

Answer 1

简单的解决方案:您可以合并所有集合(线性复杂度),然后计算在最终集合中出现n次的数字(再次线性复杂度).

使用std :: multiset(具有重复项)并合并算法.

在这里尝试一下:

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    // your code goes here
    std::multiset<int> a {1,2,3};
    std::multiset<int> b {1,2,3};

    std::multiset<int> result;
    merge( a.begin(), a.end(), b.begin(), b.end(),  
    std::inserter(result, result.begin()));
    std::cout<<result.size()<<std::endl;
    return 0;
}

结果:

成功时间:0内存:16064信号:0

6

这组工会的语义扩展到多重集(如讨论这里),但不是在我总是因子评分,他们的方式会.

采用两个多重集合的操作应该与合并两个集合的操作区分开来.假设一个参数集包含元素7的三个实例,第二个集包含两个相同值的实例.联合将只包含三个这样的值,而合并将包含五个.

从标准,25.3.5:

set操作的语义通过定义union()来包含每个元素的最大出现次数,intersection()包含最小值等,以标准方式推广到多个集合.