3622
правки
Изменения
→Построение префикс-функции по Z-функции
== Построение префикс-функции по Z-функции==
=== Постановка задачи ===
Дан массив с корректной <tex> z</tex>Z-функцией для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.
=== Описание алгоритма ===
Пусть <tex>Z</tex>-функция хранится в массиве <tex>z[1..n]</tex>. Префикс-функцию будем записывать в массив <tex>p[1..n]</tex>.
Заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 \leqslant j < z[i] </tex>, значение <tex>p[i + j] </tex> будет не меньше, чем длина подстроки с <tex> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (как изображено на рисунке).
