找到两个集合的最大公共子集的有效算法？

Question

每组都包含一堆校验和。例如：
A组：
{
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
07736dde2f8484a4a3af463e05f039e3
5b1e374ff2ba949ab49870ca24d3163a
}

B组：
{
6639e1da308fd7b04b7635a17450df7c
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f

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

执行许多这样的操作，因此我正在寻找一种有效的算法来执行此操作。 感谢您的帮助。

Answer 1

将其中一个集合放入哈希表中，然后迭代另一个集合，丢弃不在哈希表中的元素。或者，对两者进行排序并同时迭代它们，就像合并排序一样。

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

Answer 2

将它们放入哈希表中并记下确切的冲突。

Answer 3

1. 将集合 A 添加到结构中，您可以在其中查找校验和是否存在。
2. 循环Set B，检查Set A中是否存在元素，如果存在，则添加到Set C中

Set C是你的公共子集。

Answer 4

• 从集合 A 中生成有序向量/列表 A
• 从集合 B 中生成有序向量/列表 B
• 迭代有序 A,B，在较小元素上创建新步骤 - 如果相同，则添加到结果并移动两者。

当底层集合结构有序时 - 常见情况是一种树（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;
  }
}