Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики
Дата лекции: 08.09.2022
Лектор: Степанов Илья Даниилович
Монтажер: Голицын Сергей
Оператор: Жулябина Ира
00:00:00 - начало, определение бора
00:02:16 - пример бора
00:03:20 - пример: как построить бор
00:07:07 - способы хранения бора
00:10:22 - преимущества методов - таблица сравнений
00:18:34 - алгоритм построения бора на массивах
00:26:09 - задача: поддерживать множество чисел c запросами insert x и find x
00:28:50 - дополнение к задаче: erase
00:31:44 - задача, которую мы пытаетмся решить с помощью алгоритма Ахо - Корасик
00:33:47 - тривиальное решение
00:35:20 - решение
00:40:18 - определение суффиксной ссылки
00:42:04 - пример суффиксной ссылки
00:43:02 - определение go[v][c] (самый длинный суффикс строки v + c, который есть в боре)
00:45:54 - алгоритм Ахо - Корасик
01:06:35 - вопрос из зала: зачем отдельно обрабатывать случай корня
01:10:43 - асимптотика
01:12:21 - решение исходной задачи