Как использовать Trie для частичного автозаполнения

Question

Учитывая большой список слов (скажем, 1 миллион). Используя Trie, мы можем легко реализовать сопоставление префиксов. Но как я могу реализовать частичное совпадение.

Например, у нас есть список слов {"abc", "def", "lunch", "diner" ....}, как я могу получить ланч при поиске "unc"?

Является ли Три все еще хорошей структурой данных для использования в этом случае? Каковы возможные способы его эффективной реализации?

Answer 1

Наиболее распространенной структурой, используемой для такого рода приложений, является Дерево суффиксов Это действительно версия Trie, которая позволяет эффективно хранить все суффиксы для строки в одной структуре. Есть и другие варианты, но это хороший баланс между эффективностью и простотой.