Алгоритмы и структуры данных 1. Строки: хеширование, префикс-, z-функции

Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Дата лекции: 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-функцию