Алгоритмы и структуры данных. Лекция 14. Расстояние Левенштейна

Дата лекции: 14.05.24
Лектор: Артур Кулапин
Презентация лекции: drive.google.com/file/d/1NUMl...
Оператор: Дмитрий Достовалов
Монтажер: Илья Оплачкин
Сайт ВШПИ: hsse.mipt.ru
Чат абитуриентов в telegram: t.me/hsse_entering
Сообщество ВШПИ в VK: hssemiptru
00:00 - Начало
01:20 - Постановка задачи
04:05 - Алгоритм Вагнера-Фишера
20:00 - Поиск с k различиями
21:00 - Решение перебором
25:30 - Решение через dp
33:00 - Решение через графы
34:20 - Великая и ужасная величина r(p, q)
48:05 - Расчет r(p, q)
55:00 - Псевдокод
58:55 - Время работы
01:01:10 - Суффиксное дерево
1:06:15 - Построение
1:10:15 - Алгоритм Ландау-Вишкина
© ВШПИ МФТИ 2024