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

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

Pzz>>А можно контретнее? Что у тебя на входе, уже выделенная подстрока, и набор строк? Надо найти строки, в которые входит данная подстрока?

V>Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична.
V>Вот коротко что я хочу!

Надо говорить, что у тебя есть неизменные тексты, но меняющиеся запросы. И тебе нужно (возможно затратив немного времени на препроцессинг текстов) уметь быстро искать точное вхождение запроса во всех текстах сразу. Так?

Тогда классическое суффиксное дерево подходит лучше всего. Оно строится за линейное время от суммы длин текстов, в которых будет происходить поиск. И после этого для каждого входящего запроса позволяет получить все места, где запрос встречается в текстах. И делает это за линейное время от длины запроса вне зависимости от длин текстов (формально временная сложность — O(|длина запроса| + |число результатов|), так как ещё нужно перечислить все найденные места).


Если же у тебя есть какие-то дополнительные ограничения (например, тексты не влезают в память одной машины) или особенности (например, не нужно уметь искать вхождения с середины слова, как, например, если не обязательно нужно находить "нос" в слове "Ломоносов"), то возможно лучше подойдут другие варианты.

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

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

Pzz>>А можно контретнее? Что у тебя на входе, уже выделенная подстрока, и набор строк? Надо найти строки, в которые входит данная подстрока?

V>Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична.
V>Вот коротко что я хочу!

Надо говорить, что у тебя есть неизменные тексты, но меняющиеся запросы. И тебе нужно (возможно затратив немного времени на препроцессинг текстов) уметь быстро искать точное вхождение запроса во всех текстах сразу. Так?

Тогда классическое суффиксное дерево подходит лучше всего. Оно строится за линейное время от суммы длин текстов, в которых будет происходить поиск. И после этого для каждого входящего запроса позволяет получить все места, где запрос встречается в текстах. И делает это за линейное время от длины запроса вне зависимости от длин текстов (формально временная сложность — O(|длина запроса| + |число результатов|), так как ещё нужно перечислить все найденные места).


Если же у тебя есть какие-то дополнительные ограничения (например, тексты не влезают в память одной машины) или особенности (например, не нужно уметь искать вхождения с середины слова: скажем, если не обязательно нужно находить "нос" в слове "Ломоносов"), то возможно лучше подойдут другие варианты.