Здравствуйте, bnk, Вы писали:

bnk>Здравствуйте, Vladimir, Вы писали:

V>>Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки.

bnk>Почему не подходит?
bnk>Вроде задача похожа на твою 1-в-1 (поиск статей по содержащемуся в их заголовке слову)

Как я понял, у автора темы в задаче меняются запросы, но не меняются тексты, в которых происходит поиск. По ссылке же обратная ситуация описана.

bnk> Попробуй посмотреть вот например, описано как сделать full-text-search с помощью trie (префиксного дерева).
bnk>https://www.toptal.com/algorithms/needle-in-a-haystack-a-nifty-large-scale-text-search-algorithm

Не надо туда смотреть — там ерунда. Описанный по ссылке "алгоритм" не будет работать. Например, он не найдёт запрос "aab" в тексте "xaaabx" (или в аналоге где слова вместо букв "x a a a b x"). То есть даже для поиска одного образца в одном тексте метод бесполезен. Чего уж там говорить об более сложных случаях. Забавно, конечно, что автор проверяет производительность кода, но не проверяет его правильность. Хотя неправильный ответ можно получить и куда проще, и куда быстрее

Если интересно, то описанная по ссылке задача (много статических запросов для поиска в динамическом тексте) решается правильно, например, классическим алгоритмом Ахо-Корасик (про то, что связь с trie есть, но она не такая, по ссылке тоже написано)


bnk>То есть, то того что дерево "префиксное", вовсе не означает что оно может использоваться только для поиска с начала строки.
bnk>Это просто название структуры данных такое.

Это да

Здравствуйте, bnk, Вы писали:

bnk>Здравствуйте, Vladimir, Вы писали:

V>>Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки.

bnk>Почему не подходит?
bnk>Вроде задача похожа на твою 1-в-1 (поиск статей по содержащемуся в их заголовке слову)

Как я понял, у автора темы в задаче меняются запросы, но не меняются тексты, в которых происходит поиск. По ссылке же обратная ситуация описана.

bnk> Попробуй посмотреть вот например, описано как сделать full-text-search с помощью trie (префиксного дерева).
bnk>https://www.toptal.com/algorithms/needle-in-a-haystack-a-nifty-large-scale-text-search-algorithm

Не надо туда смотреть — там ерунда. Описанный по ссылке алгоритм не будет работать правильно. Например, он не найдёт запрос "aab" в тексте "xaaabx" (или в аналоге где слова вместо букв "x a a a b x"). То есть даже для поиска одного образца в одном тексте метод плох. Чего уж там говорить об более сложных случаях.

Если интересно, то описанная по ссылке задача (много статических запросов для поиска в динамическом тексте) решается правильно, например, классическим алгоритмом Ахо-Корасик (про то, что связь с trie есть, но она не такая, по ссылке тоже написано)


bnk>То есть, то того что дерево "префиксное", вовсе не означает что оно может использоваться только для поиска с начала строки.
bnk>Это просто название структуры данных такое.

Это да