На чём держится
бор
Статьи
SRT
Алгоритм
Сортировка подсчётом и поразрядная
Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n.
O(n + k) и O(d·(n + b))
2 задачи
DS
Структура данных
Бор (префиксное дерево)
Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса.
O(L) на вставку и поиск слова длины L
2 задачи
STR
Алгоритм
Алгоритм Ахо — Корасик
Все вхождения тысяч слов за один проход: бор из слов плюс ссылки отказа, как у префикс-функции.
O(n + Σ|wᵢ| + z)
1 задача
Задачи
Часто рядом
классика 3 собеседования 2 в проде 2 поиск в тексте 2 сети 2 сортировка 1 массив 1 устойчивость 1 префиксные суммы 1 битовые трюки 1 контроль версий 1 дерево 1