3622
правки
Изменения
→Описание алгоритма
=== Описание алгоритма ===
Пусть <tex>Z</tex>-функция хранится в массиве <tex>z[1..n],</tex> префикс-функцию будем записывать в массив <tex>p[1..n]</tex>.
Пойдем по массиву <tex>z</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> (видно из рисункакак изображено на рисунке).
Также заметим, что если мы уже установили в какую-то позицию значение с позиции <tex>k</tex>, где <tex>k < i</tex>, то такое изменение только уменьшит значение <tex> p[i + j]</tex>, действительно, значение после первого присвоения <tex>p_{old}[i + j] = i + j - k + 1 > i + j - i + 1 = p_{new}[i + j]</tex>. В итоге получаем алгоритм: идем слева направо по массиву <tex>z</tex> и пусть мы сейчас находимся на позиции <tex>i</tex>, тогда пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex> значение <tex> j + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0.. z[i] - 1</tex>, пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.
