Программирование основных алгоритмов 10. Бор (trie). Ахо-Корасик.

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

Дата лекции: 12.04.2023
Лектор: Кулапин Артур Евгеньевич

00:00:00 - интро
00:00:04 - постановка задачи на лекцию
00:01:34 - определение бора (trie) и пример
00:07:25 - асимптотики в случае разных контейнеров для хранения
00:10:49 - НКА
00:17:03 - определение link(v), to(v, σ)
00:25:29 - to(link(v), c) = link(to(v, c))
00:32:42 - алгоритм построения автомата Ахо-Корасик
00:41:03 - сжатая суффиксная ссылка
00:48:50 - пример работы алгоритма
00:59:40 - время построения автомата и работы алгоритма
01:03:24 - Ахо-Корасик для одной строки

Монтажер: Вашкевич Егор
Оператор: Вашкевич Егор