이 데이터 구조는 무엇입니까?

Question

임의의 길이와 수의 이진 문자열 집합 (중복되지 않음)이 주어졌으며 다른 문자열의 접두사가 있는지 여부를 알아야합니다. 작은 길이와 작은 길이의 문자열에 대해서는 간단합니다. 접두사가 일치 할 때마다 각 문자열을 읽어 바이너리 트리를 작성하기 만하면됩니다. 그러나 길이가 긴 문자열을 많이 사용하면이 방법은 효율적이지 않습니다. . 이것에 대한 올바른 데이터 구조와 알고리즘이 무엇인지 궁금 할뿐입니다. 호프만 나무? 시도 (기수)? 또는 아무것도? 감사.

Answer 1

나는 트라이와 함께 갈 것이다. 트 리를 사용하여 모든 문자열을 삽입하여 각 문자열의 마지막 노드에 플래그를 표시 한 다음 각 문자열에 대해 경로를 따라 이동하고 페이지의 노드에 플래그가 설정되어 있는지 확인합니다. 그렇다면 해당 노드에서 끝나는 문자열이 분석중인 문자열의 접두사입니다.

n = 문자열 수 및 k = 평균 길이라고 가정하고 삽입 및 분석 모두 O (kn)을 취합니다.

프리픽스 트리 (단일 문자보다 긴 노드를 가진 트라이)가 더 효율적이지만 구현하기 쉽지는 않습니다.