На чём держится
автомат
Статьи
STR
Алгоритм
Префикс-функция и КМП
Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки.
O(n + m)
2 задачи
STR
Алгоритм
Алгоритм Ахо — Корасик
Все вхождения тысяч слов за один проход: бор из слов плюс ссылки отказа, как у префикс-функции.
O(n + Σ|wᵢ| + z)
1 задача
STR
Структура данных
Суффиксный автомат
Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход.
O(n)
2 задачи
Задачи
Часто рядом
поиск в тексте 3 потоковая обработка 3 олимпиады 3 биоинформатика 2 классика 2 предподсчёт 1 амортизация 1 собеседования 1 бор 1 безопасность 1 сети 1 в проде 1