В ядре Linux есть поиск строки, который ускоряется за счёт пропуска символов
В
Допустим, ищем
Первое сравнение: последняя
Можно сдвинуть шаблон сразу на пять позиций. При меньшем сдвиге
Реализация ядра заранее строит две таблицы: для сдвига по несовпавшему символу и по уже совпавшему суффиксу. Затем выбирает больший из допустимых сдвигов.
Но у этой реализации есть ограничение: она может пропустить совпадение на границе двух блоков данных. Например, если один блок заканчивается на
Поэтому прямо в комментарии к исходнику для фильтрации и обнаружения вторжений рекомендуют KMP, который умеет находить такие совпадения.
Выбор алгоритма здесь зависит и от скорости, и от того, как данные поступают на обработку.
В
lib/ts_bm.c реализован алгоритм Бойера - Мура. Он сравнивает шаблон с текстом справа налево и при несовпадении может перескочить сразу через несколько позиций.Допустим, ищем
ERROR:
Текст: ABCDXERROR
Шаблон: ERROR
↑
Первое сравнение: последняя
R шаблона против X в тексте. Символа X в ERROR вообще нет.Можно сдвинуть шаблон сразу на пять позиций. При меньшем сдвиге
X всё ещё находился бы внутри проверяемого участка, поэтому совпадение невозможно.Реализация ядра заранее строит две таблицы: для сдвига по несовпавшему символу и по уже совпавшему суффиксу. Затем выбирает больший из допустимых сдвигов.
Но у этой реализации есть ограничение: она может пропустить совпадение на границе двух блоков данных. Например, если один блок заканчивается на
ERR, а следующий начинается с OR.Поэтому прямо в комментарии к исходнику для фильтрации и обнаружения вторжений рекомендуют KMP, который умеет находить такие совпадения.
Выбор алгоритма здесь зависит и от скорости, и от того, как данные поступают на обработку.
❤1👍1