какая структура данных для этого?

Question

Мне присваивался набор (без дублирования) двоичных строк с произвольной длиной и числом, и нужно выяснить, есть ли какая-либо строка, префикс другой строки. для небольшого набора и строки с малой длиной, просто, просто создайте двоичное дерево, прочитав каждую строку, всякий раз, когда я нахожу совпадение префикса, im done.but с большим количеством строк с большой длиной, этот метод не будет эффективным , просто интересно, какая будет правильная структура данных и алгоритм для этого. дерево хаффмана? пытается (дерево оснований)? или что-нибудь? Благодарю.

Answer 1

Я бы пошел с trie. Используя trie, вставьте все строки так, чтобы последний узел каждой строки был помечен флагом, затем для каждой строки прогуливался по его пути и проверял, установлен ли какой-либо узел на странице установленным флагом. Если да, то строка, заканчивающаяся на этом узле, является префиксом строки, которую вы анализируете.

Предполагая, что n = количество строк и k = средняя длина, вставка и анализ обоих берут O (kn).

Дерево префикса (trie с узлами длиннее одного символа) может быть более эффективным, но не столь простым в реализации.