Задачник Базовый курс EN

На чём держится

суффиксные структуры

Статьи

STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи STR Структура данных Суффиксный автомат Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход. O(n) 2 задачи STR Алгоритм Преобразование Барроуза — Уилера Перестановка, которая сжимает текст и служит по нему указателем: обратный поиск, LF и выравнивание ридов. O(m) на подсчёт образца, O(m + k·s) на k мест 2 задачи

Задачи

Склейка Сколько разных кусков Суффиксы генома по разрядам Счёт по перестановке Эхо Куда легли риды Сложность по Лемпелю — Зиву Фраза k раз

Часто рядом

поиск в тексте 3 биоинформатика 2 поисковики 2 сжатие 2 олимпиады 2 сортировка 1 двоичный поиск 1 предподсчёт 1 автомат 1 потоковая обработка 1 похожесть 1 в проде 1