АиСД S03E10. Z-функция. Бор
Алгоритмы и структуры данных. Семестр 3. Лекция 10.
На десятой лекции мы продолжили говорить про алгоритмы на строках, рассмотрели алгоритмы построения Z-функции и про структуру данных "бор".
Университет ИТМО, 2019 г.
Алгоритмы и структуры данных. Семестр 3. Лекция 10.
На десятой лекции мы продолжили говорить про алгоритмы на строках, рассмотрели алгоритмы построения Z-функции и про структуру данных "бор".
Университет ИТМО, 2019 г.
Пікірлер: 10
У вас очень сильно улучшилось качество видео и Вы теперь меньше переживаете, это сразу заметно. Очень круто, спасибо за видео!
Исправление на 23:16 c r=0 на r=1 не верно, например если r = 1, i=10, z[i-l]=0, то z[i] станет равно -9 и из-за этого будет обращение к неверному индексу строки. Чтобы было правильно, нужно первое присвоение z[i] (строка сразу внутри цикла for) обернуть в if(i Проверить корректность самостоятельной реализации этого алгоритма можно тут: codeforces.com/edu/course/2/lesson/3/3/practice
@pavelmavrin
3 жыл бұрын
Накосячил немножко, да. Надо на самом деле сделать z[i] = max(0, min(z[i - l], r - i)), чтобы оно в отрицательные числа не уходило никогда
Для строки cabab возвращет z-функция одни нули. хотя ab = ab какой алгоритм сделать чтобы могло с такими тоже работать? Самый прикол, что и префикс-функция тоже нули на этой строке дает.
@pavelmavrin
Жыл бұрын
А что нужно сделать со строкой?
2:43 почему блин 4?
@user-dc3pk2kp4e
3 жыл бұрын
все понял
@asylainurgali6732
2 жыл бұрын
@@user-dc3pk2kp4e почему же?
@antiloh1336
Жыл бұрын
@@user-dc3pk2kp4e Объясни
@antiloh1336
Жыл бұрын
А все, понял.