748
правок
Изменения
→Постановка задачи
Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с Z-функцией для строки <tex>s</tex>.
===Описание алгоритма=== Пусть префикс функция хранится в массиве <tex>P[0 ... n - 1]</tex>. Z-функцию будем записывать в массив <!tex>Z[0 ... n-1]</tex>. Заметим, что если <tex>P[i]>0</tex>, то мы можем заявить, что <tex>Z[i- P[i]+1]</tex> будет не меньше, чем <tex>P[i]</tex>.<br><br>Так же заметим, что после такого прохода в <tex>Z[1]</tex> будет максимальное возможное значение. Далее будем поддерживать инвариант: в <tex>Z[i]</tex> будет максимальное возможное значение.<br>Пусть в <tex>Z[i] =z > 0</tex>, рассмотрю <tex>j<k</tex>, <tex>Z[j]=k</tex> и <tex>Z[i+j]=Описание алгоритма=k_1</tex>. Заметим, что <tex>s[0 ... z-1]</tex> совпадает с <tex>s[i...z-1]</tex> и тогда возможны три случая:# <tex>k<k_1</tex>. Тогда мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>. <!--(см картинку)--># <tex>k<z-j</tex> и <tex>k>k_1</tex>. Тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>. <!--(см картинку)--># <tex>k>z-j</tex> и <tex>k>k_1</tex>. Тогда понятно, что <tex>Z[i+j]= z-j</tex>. <!--(см картинку)-->
===Псевдокод===
