Быстро фильтрация строкового набора подстрокой?

Да, вы можете, например, создать индекс для всех комбинаций символов в строках. Строка вроде «hello» будет добавлена ​​в индексы для «he», «el», «ll» и «lo». Для поиска строки «ад» вы должны получить индекс всех строк, которые существуют во всех индексах «он», «эль» и «ll», а затем просмотреть их в цикле для проверки фактического содержания в строках.

Если вы можете предварительно обработать коллекцию, вы можете делать много разных вещей.

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

Если вы собираетесь многократно искать один и тот же текст, то, вероятно, стоит использовать суффиксное дерево . При правильном применении вы можете добиться линейной обработки по времени для большинства проблем со строками. Если нет, то на практике вы не сможете добиться большего успеха, чем Рабина-Карпа , который основан на хешировании и линейен по ожидаемому времени.

Существует множество свободно доступных реализаций. суффиксные деревья. См., Например, эту реализацию C или для Java,

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

Помимо подобных вещей, просто итерация - вот и все.

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

Если это где-нибудь, то вам в значительной степени нужно перебрать весь список, если только вы не list настолько велик, и запрос выполняется достаточно часто, поэтому стоит создать более сложное решение для индексации.

Если подстрока находится в начале строки, это просто. Отсортируйте список, найдите начало / конец с помощью бисситонного поиска и выберите это подмножество.