Эффективный алгоритм, чтобы найти максимальное общее подмножество из двух наборов?

Question

Каждый набор содержит кучу контрольных сумм. Например:
Комплект A:
{
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
07736dde2f8484a4a3af463e05f039e3
5b1e374ff2ba949ab49870ca24d3163a
}

Набор B:
{
6639e1da308fd7b04b7635a17450df7c
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
}

Максимальное общее подмножество A и B:
{
4445968d0e100ad08323df8c895cea15
a67f8052594d6ba3f75502c0b91b868f
} * * Тысяча двадцать-один

Многие из этих операций будут выполнены, поэтому я ищу эффективный алгоритм для этого. Спасибо за вашу помощь.

Answer 1

Поместите один из наборов в хеш-таблицу и переберите другой, отбрасывая элементы, которых нет в хеш-таблице. В качестве альтернативы сортируйте оба и выполняйте их одновременно, как в сортировке слиянием.

EDIT: последний метод создает отсортированный результат. Я должен добавить, что если наборы имеют разнородные размеры и они предварительно отсортированы (скажем, потому что вы делаете кучу пересечений), то вы можете добиться значительного улучшения производительности, используя «неограниченный» двоичный поиск, чтобы пропустить большой список.

Answer 2

Вставьте их в хеш-таблицу и отметьте точные столкновения.

Answer 3

1. Добавить набор A в структуру, где вы можете найти, существует ли контрольная сумма.
2. Loop Set B, проверьте, существует ли элемент в Set A, если он существует, добавьте в Set C

Набор 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;
  }
}