查找两组最大公共子集的有效算法？

每组包含一堆校验和。例如：
集A：
{
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
07736dde2f8484a4a3af463e05f039e3
5b1e374ff2ba949ab49870ca24d3163a
}查找两组最大公共子集的有效算法？

集B：
{
6639e1da308fd7b04b7635a17450df7c
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
}

A和B的最大公共子集是：
{
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
}

很多这些操作都将被执行，所以我在寻找一个有效的算法。感谢您的帮助。

来源

2010-03-09 datasunny

你想被称为集合的交集是什么。 – 2010-03-09 01:52:29

我在回答中假设你正在处理大集合。如果你正在处理大量的小集合，你的方法会简单得多 - 只需对集合进行排序，然后将这两个步骤迭代即可。 – Steve314 2010-03-09 09:20:14

将它们粘在散列表中并记下确切的冲突。

来源

2010-03-09 01:45:56

将其中一个集合放在散列表中，并遍历另一个集合，放弃不在散列中的元素。或者，同时对它们进行排序和迭代，就像合并排序一样。

编辑：后一种方法创建一个排序的结果。我应该补充说，如果这些集合的大小相差很大，并且它们被预先分类（说因为你正在做一堆交叉），那么你可以通过使用“无界”二进制搜索来跳过大名单。

来源

2010-03-09 01:46:43 user287792

将Set A添加到可以找到是否存在校验和的结构中。
环路B组，检查是否在集合A中存在元素，如果存在，添加到C组

集C是常见的子集。

来源

2010-03-09 01:47:09

制作有序的矢量/列表一个从组B组A
制作有序的矢量/ B名单
遍历有序更小的元素在A，B制作新的一步 - 如果相同，添加到restult和同时移动。

当底层组结构有序 - 常见的情况是一种树（BST，AVL等）， - 那么你需要只有最后一步执行。

为了使最后一步清楚，这里是它的伪代码：

a = A.begin(); b = B.begin(); 
while(a!=A.end() && b!=B.end()){ 
    if(*a==*b){ 
    results.add(a); 
    ++a; ++b; 
    } else if(*a < *b) { 
    ++a; 
    } else { 
    ++b; 
    } 
}

来源

2011-08-24 09:29:06

查找两组最大公共子集的有效算法？

回答

相关问题