Efficient algorithm to find a maximum common subset of two sets?

Each set contains bunch of checksums. For example:

Set A:

{

4445968d0e100ad08323df8c895cea15

a67f8052594d6ba3f75502c0b91b868f

07736dde2f8484a4a3af463e05f039e3

5b1e374ff2ba949ab49870ca24d316开发者_开发问答3a

}

Set B:

{

6639e1da308fd7b04b7635a17450df7c

4445968d0e100ad08323df8c895cea15

a67f8052594d6ba3f75502c0b91b868f

}

The maximum common subset of A and B is:

{

4445968d0e100ad08323df8c895cea15

a67f8052594d6ba3f75502c0b91b868f

}

A lot of these operations will be performed, so I'm looking for an efficient algorithm to do so. Thanks for your help.

Put one of the sets in a hash table and iterate through the other, discarding elements that aren't in the hash. Alternatively, sort both and iterate through them simultaneously, as in merge sort.

EDIT: The latter method creates a sorted result. I should add that if the sets are of widely disparate sizes and they're presorted (say because you're doing a bunch of intersections), then you can realize a large performance improvement by using "unbounded" binary search to skip ahead in the large list.

Stick them in a hashtable and note the exact collisions.

1. Add Set A to a structure where you can find if a checksum exists.
2. Loop Set B, check if element exists in Set A, if it exists, add to Set C

Set C is your common subset.

• Make ordered vector/list A from Set A
• Make ordered vector/list B from Set B
• Iterate over ordered A,B making new step on smaller element - if identical, add to restult and move both.

When underlying set structure is ordered - common case is a kind of Tree (BST,AVL etc.), - then you need only last step to perform.

To make last step clear, here is it's pseudocode:

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;
  }
}