Изменения

|definition = '''Z-функция''' (англ. ''Z-function'') от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Более формально, <tex>Z[i](s) = \max k \mid s[i\, \mathinner{\ldotp\ldotp}ldots \, i + k] = s[0 \mathinner{\ldotp\ldotp} ldots k]</tex>. <!-- проинлайнил \twodots из clrscode -->

Пусть префикс функция хранится в массиве <tex>P[0 ... \ldots n - 1]</tex>. Z-функцию будем записывать в массив <tex>Z[0 ... \ldots n-1]</tex>. Заметим, что если <tex>P[i]>0</tex>, то мы можем заявить, что <tex>Z[i-P[i]+1]</tex> будет не меньше, чем <tex>P[i]</tex>.

Пусть в <tex>Z[i] = z > 0</tex>, рассмотрю <tex>j<z</tex>, <tex>Z[j]=k</tex> и <tex>Z[i+j]=k_1</tex>. Пусть <tex>b_1=s[0...\ldots k-1]</tex>, <tex>b_2=s[j...\ldots j+k-1]</tex>, <tex>b_3=s[0...\ldots z-1]</tex>. Тогда заметим, что <tex>b_3 = s[i...\ldots i+z-1]</tex> и тогда возможны три случая:

#: Тогда <tex>b_1 \subset s[0...\ldots k_1-1]=s[i+j...\ldots i+j+k_1-1]</tex> и тогда очевидно, что мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>.

#: Тогда <tex>b_1 = b_2 \subset b_3 = s[i...\ldots i+z-1] \Rightarrow b_1 = s[i+j...\ldots i+j+k-1]</tex> и тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>.

#: Тогда <tex>b_1 = b_2 </tex>, но <tex>b_2</tex> не является подстрокой строки <tex>b_3</tex> (так как<tex>j+k-1 > z</tex>). Так как известно, что <tex>s[z] \ne s[i+z]</tex>, то <tex>s[0...\ldots z-j] = s[i+j...\ldots i+z-1]</tex> и тогда понятно, что <tex>Z[i+j]=z-j</tex>.