Изменения

Пусть в <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...k-1]</tex>, <tex>b_2=s[j...j+k-1]</tex>, что <tex>b_3=s[0 ... z-1]</tex> совпадает с . Тогда заметим, что <tex>b_3 = s[i...i+z-1]</tex> и тогда возможны три случая:

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

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

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