hw искать подстроку в списке проиндексированных строк?

Question

Я реализую словарь, в котором ключ является строкой ключевого слова. Предположим, у меня есть следующие ключи в словаре.

мат хон СБ хон lat hon

Теперь, если я найду одно ключевое слово, предположим, что mathon будет искать его в постоянное время. Но если я хочу искать hon Я хочу, чтобы все три слова были получены в постоянное время или за минимальное возможное время, как в случай поиска в Google. Каким должен быть мой подход? и является ли словарь правильной структурой данных для цели?

значение словаря - это список элементов, которые мне нужно отобразить пользователю, и поиск может быть основан на нескольких ключевых словах.

Answer 1

гаддаг, как описано в этой статье , вероятно, является вашей лучшей ставкой. это вариант с деревом, который позволяет начать поиск в любом месте слова и перемещаться как вперед, так и назад. это не O (1) поиск, но он довольно быстрый и разумно использует пространство.

edit: и для нескольких ключевых слов вы можете просто выполнить поиск по каждому ключевому слову индивидуально, а затем выполнить набор пересечения или объединения в зависимости. скорее всего, быстрее, чем вы думаете; по крайней мере, стоит реализовать его в качестве самого простого алгоритма и отбросить его, только если он оказывается фактическим узким местом при профилировании.