Нахождение самого длинного общего префикса в дереве троичного поиска

Question

Нахождение самого длинного общего префикса в дереве троичного поиска

Я реализую троичное дерево поиска для 20000 слов. Я хочу знать алгоритм, чтобы найти самый длинный общий префикс (префикс, который разделяется по крайней мере 2 слова)? В любом случае можно найти самый длинный общий префикс в дереве (без троичного дерева поиска)

1

algorithm dictionary sorting data-structures ternary-search-tree

Источник

user1204685 10 фев '13 в 17:09

1 ответ

Другие вопросы по тегам algorithm dictionary sorting data-structures ternary-search-tree

user1290371 11 фев '13 в 21:40 2013-02-11 21:40 · Answer 1 · 2013-02-11 21:40

Существует очень простое решение и линейная сложность. Вы знаете, что Rabin-Karp - это алгоритм сопоставления строк, в котором для этого используется хеширование. Идея заключается в создании хеш-таблицы. Вы просматриваете все слова и на каждой длине 1, 2, .. len(слово) вы помещаете ключ (значение хеш-функции для этой подстроки) в таблицу, и когда у вас уже есть этот ключ в таблице, это означает, что у вас есть 2 слова (как минимум) с этим значением хеша. Тогда вам нужно только найти самый длинный индекс, который имеет это свойство.