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

Что решает

похожесть

Статьи

STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Структура данных Суффиксный автомат Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход. O(n) 2 задачи STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи STR Структура данных BK-дерево Все пароли в одной-двух правках от данного: неравенство треугольника отрезает целые ветви — и где оно перестаёт помогать. O(N · глубина) на построение 1 задача DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи DP Алгоритм Выравнивание последовательностей Лучшее сопоставление двух последовательностей с очками за замены и пропуски: целиком, по кускам и с проверкой на случайность. O(m · n) 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи

Задачи

Ошибки секвенатора Пары из корзин Два частотных словаря Общий кусок Похожие пароли Пропуски одним куском Самый длинный общий кусок Словарь двух томов Словарь опечаток Соседи пароля Три редакции

Часто рядом

классика 4 поиск в тексте 3 собеседования 3 динамика 3 матрица 3 хеширование 2 случайность 2 дедупликация 2 в проде 2 поисковики 2 биоинформатика 2 сравнение версий 2