두 집합의 최대 공통 부분 집합을 찾는 효율적인 알고리즘?

Question

각 세트에는 일련의 체크섬이 포함되어 있습니다.
세트 A : :

세트 B {
4445968d0e100ad08323df8c895cea15
07736dde2f8484a4a3af463e05f039e3
5b1e374ff2ba949ab49870ca24d3163a

a67f8052594d6ba3f75502c0b91b868f} {

6639e1da308fd7b04b7635a17450df7c
4445968d0e100ad08323df8c895cea15
01,235,164 예

이

A와 B의 최대 공통 부분 집합이다}
a67f8052594d6ba3f75502c0b91b868f :
{
4445968d0e100ad08323df8c895cea15
}
a67f8052594d6ba3f75502c0b91b868f

이러한 작업의 많은 수행됩니다, 그래서 찾고 있어요 그렇게하는 효율적인 알고리즘. 도움 주셔서 감사합니다.

Answer 1

해시 테이블에 고정하고 정확한 충돌을 기록하십시오.

Answer 2

해시 테이블에 세트 중 하나를 넣고 해시 테이블에있는 다른 요소를 반복하여 해시에없는 요소를 버립니다. 또는 병합 정렬과 같이 둘 다 정렬하고 동시에 반복 할 수 있습니다.

EDIT : 후자의 방법은 정렬 된 결과를 만듭니다. 나는 세트가 넓고 다른 크기이고 미리 정렬되어 있다면 (말하자면 교차로를하고 있기 때문에), "무제한"2 진 검색을 사용하여 큰 성능 향상을 실현할 수 있다고 덧붙여 야합니다. 큰 목록.

Answer 3

1. 체크섬이 있는지 확인할 수있는 구조에 집합 A를 추가하십시오. 존재하는 경우
2. 요소가 세트 A에있는 경우 루프 세트 B가, 확인, C

설정 C 설정에 추가하면 일반적인 하위 집합입니다.

Answer 4

• 만들기 주문 벡터 /리스트 A는 세트 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; 
    } 
}