Тёмный

АиСД S03E10. Z-функция. Бор 

Pavel Mavrin
Подписаться 32 тыс.
Просмотров 6 тыс.
50% 1

Алгоритмы и структуры данных. Семестр 3. Лекция 10.
На десятой лекции мы продолжили говорить про алгоритмы на строках, рассмотрели алгоритмы построения Z-функции и про структуру данных "бор".
Университет ИТМО, 2019 г.

Опубликовано:

 

30 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 10   
@elizabethsvirskaya7110
@elizabethsvirskaya7110 4 года назад
У вас очень сильно улучшилось качество видео и Вы теперь меньше переживаете, это сразу заметно. Очень круто, спасибо за видео!
@denisbkh
@denisbkh 4 года назад
Исправление на 23:16 c r=0 на r=1 не верно, например если r = 1, i=10, z[i-l]=0, то z[i] станет равно -9 и из-за этого будет обращение к неверному индексу строки. Чтобы было правильно, нужно первое присвоение z[i] (строка сразу внутри цикла for) обернуть в if(i < r) Проверить корректность самостоятельной реализации этого алгоритма можно тут: codeforces.com/edu/course/2/lesson/3/3/practice
@pavelmavrin
@pavelmavrin 4 года назад
Накосячил немножко, да. Надо на самом деле сделать z[i] = max(0, min(z[i - l], r - i)), чтобы оно в отрицательные числа не уходило никогда
@musicits_fun
@musicits_fun Год назад
Для строки cabab возвращет z-функция одни нули. хотя ab = ab какой алгоритм сделать чтобы могло с такими тоже работать? Самый прикол, что и префикс-функция тоже нули на этой строке дает.
@pavelmavrin
@pavelmavrin Год назад
А что нужно сделать со строкой?
@ТестТест-в3ъ
@ТестТест-в3ъ 3 года назад
2:43 почему блин 4?
@ТестТест-в3ъ
@ТестТест-в3ъ 3 года назад
все понял
@asylainurgali6732
@asylainurgali6732 2 года назад
@@ТестТест-в3ъ почему же?
@antiloh1336
@antiloh1336 Год назад
​@@ТестТест-в3ъ Объясни
@antiloh1336
@antiloh1336 Год назад
А все, понял.
Далее
АиСД S03E11. Алгоритм Ахо-Корасик
1:30:21
АиСД S03E10. Z-функция. Бор
1:28:34
Просмотров 5 тыс.
JUJU HAS IT ALL! | Brawl Stars Animation
00:53
Просмотров 6 млн
АиСД S01E14. Хеш-таблицы
1:18:28
Просмотров 4,1 тыс.
20241017 Плоткин А.В.
1:17:09
Просмотров 11
Алгоритмы. Префикс-функция
31:51
АиСД S03E14. Цифровой бор
1:26:09
Просмотров 1,3 тыс.
Z algorithm illustration
12:50
Просмотров 8 тыс.