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

Что решает

сравнение версий

Статьи

STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении.

O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой

Задачи

Старые блоки в новом файле Сколько строк поменялось Три редакции

Часто рядом

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