748
правок
Изменения
м
→Описание алгоритма
#: Тогда <tex>s[0...k-1]</tex> равна <tex>s[j...j+k-1]</tex>, которая является подстрокой строки <tex>s[0...z-1]</tex>, которая равна <tex>s[i...i+z-1]</tex>. Значит точно можно сказать, что <tex>s[0...k-1]</tex> равна <tex>s[i+j...i+j+k-1]</tex> и тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>.
# <tex>k>z-j</tex> и <tex>k>k_1</tex>.
#: Тогда <tex>s[0...k-1]</tex> равна <tex>s[j...j+k-1]</tex>, которая не является подстрокой строки <tex>s[0...z-1]</tex> (так как<tex>j+k-1 > z</tex>). Так как известно, что <tex>s[z]</tex> не равен <tex> 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>.
<br>
