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

Question

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

Answer 1

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

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

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