Алгоритмы (основной поток) 3. Алгоритм Ахо-Корасик

0:00:55 - Описание обозначений
0:02:05 - Алгоритм Ахо-Корасик
0:07:20 - Применение алгоритма
0:08:55 - Задача о поиске вхождений паттерна в текст
0:10:35 - Решение поставленной задачи
0:13:25 - Суффиксные ссылки
0:22:50 - Использование алгоритма с суффиксными ссылками
0:31:50 - Работа со сжатыми суффиксными ссылками
0:39:45 - Применение ССС
0:46:10 - Реализация бора на массиве
0:51:30 - Реализация на map
1:01:45 - Оптимизации
1:06:00 - Возвращение к поставленной задаче
========================
Дата лекции: 20.09.2019
Лектор: Крахмалев Д. С.
Съёмка: Рухадзе
Монтаж: Кухтенков

[lectory_fpmi]

​0:00:55 - Описание обозначений
0:02:05 - Алгоритм Ахо-Корасик
0:07:20 - Применение алгоритма
0:08:55 - Задача о поиске вхождений паттерна в текст
0:10:35 - Решение поставленной задачи
0:13:25 - Суффиксные ссылки
0:22:50 - Использование алгоритма с суффиксными ссылками
0:31:50 - Работа со сжатыми суффиксными ссылками
0:39:45 - Применение ССС
0:46:10 - Реализация бора на массиве
0:51:30 - Реализация на map
1:01:45 - Оптимизации
1:06:00 - Возвращение к поставленной задаче

[rationaleks]

11:44 асимптотика будет не O(P*|T|), а O(max{|p_i|} * |T|). Это так, потому что для каждой стартовой позиции нам надо пройти не больше, чем длину максимальной ветви бора, а это и есть длина наибольшего слова в словаре.