668
правок
Изменения
→Построение префикс-функции по Z{{---}}функции
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>\mathrm{while}</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Поскольку внутри цикла <tex>\mathrm{while}</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>\mathrm{while}</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.
== Построение префикс-функции по Z{{---}}функции==
=== Постановка задачи ===
Дан массив с корректной <tex> z-</tex>{{---}} функцией для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс{{---}}функцией для строки <tex>s</tex>.
=== Описание алгоритма ===
