Алгоритмы и структуры данных

Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Дата лекции: 01.09.2022

Лектор: Степанов Илья Даниилович

Монтажер: Голицын Сергей

Оператор: Жулябина Ира

// немного запоздалая запись первой лекции)

00:00:00 — начало; строка, хеширование

00:01:54 — как умножаем и складываем символы с числами в хешировании

00:08:34 — утверждение о вероятности коллизии случайных строк

00:17:00 — утверждение о вероятности коллизии при выборе простого числа в качестве модуля

00:20:40 — задача проверки равенства двух подстрок

00:26:07 — задача проверки вхождения одной строки в другую через хеширование

00:29:58 — префикс-функция

00:33:25 — определение супрефикса (суффикс, равный префиксу той же длины)

00:34:17 — утверждение о длинах супрефиксов

00:39:33 — алгоритм построения префикс-функции

00:46:01 — пример

00:48:18 — асимптотика

00:51:43 — задача о проверке вхождения одной строки в другую через префикс-функцию

00:59:00 — z-функция

01:00:45 — определение z-блока (подстрока, равная префиксу)

01:01:31 — возвращение к алгоритму построения z-функции

01:15:00 — вывод асимптотики

01:19:00 — задача о проверке вхождения одной строки в другую через z-функцию

Источник: vk.com

Комментарии: