Алгоритмы и структуры данных. Семестр 3. Лекция 10. На десятой лекции мы продолжили говорить про алгоритмы на строках, рассмотрели алгоритмы построения Z-функции и про структуру данных "бор". Университет ИТМО, 2019 г.
Исправление на 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
Для строки cabab возвращет z-функция одни нули. хотя ab = ab какой алгоритм сделать чтобы могло с такими тоже работать? Самый прикол, что и префикс-функция тоже нули на этой строке дает.