Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики
Дата лекции: 15.09.2022
Лектор: Степанов Илья Даниилович
Монтажер: Голицын Сергей
Оператор: Жулябина Ира
00:00:00 - начало; решение задачи c прошлой лекции (вхождение всех словарных слов в строку)
00:05:30 - сжатая суффиксная ссылка
00:08:24 - асимптотика решения задачи c прошлой лекции
00:10:36 - суффиксный массив - постановка задачи
00:11:43 - пример
00:12:32 - решение
00:21:41 - сортируем строки - код
00:25:15 - переход от строк длины 2^k к 2^(k + 1)
00:59:14 - асимптотика
00:59:51 - массив LCP - longest common prefix
01:04:27 - утверждение про LCP (доказательтсво: 01:06:40)
01:10:30 - массив pos, обратный к p, - нахождение
01:11:30 - алгоритм подсчета LCP
01:16:25 - применение массива LCP
01:20:50 - утверждение о длине LCP двух подстрок
01:24:03 - второе применение LCP