Изменения

Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>. Покажем, что массивы <tex>q</tex> и <tex>z</tex> будут совпадать.  Так как значение в <tex>z[0]</tex> неопределено, то мы рассматриваем ненулевые индексы массива <tex>z</tex>. Если <tex>z[i] = 0</tex>, то по алгоритму <tex>s[i]</tex> будет отличаться от <tex>s[0]</tex>. Тогда, при подсчёте Z-функции для полученной строки, мы получим, что <tex>q[i] = 0</tex>, ведь <tex>s[i] \neq s[0]</tex>. Значит, если <tex>z[i] = 0</tex>, то <tex>z[i] = q[i]</tex>.

Если Рассмотрим значения <tex>z[i] = \ne 0</tex>. В этом случае <tex>s[i]</tex> является началом префикса исходной строки. Будем называть подстроки, совпадающие с префиксом строки, то и блоками. Возможны три случая:* Мы полностью записали рассматриваемый блок длиной <tex>qz[i] = 0</tex>, так как . По определению Z-функции <tex>sq[i] \ne s= z[0i]</tex> (.* Мы записали часть рассматриваемого блока <tex>b_1</tex> и прервались, чтобы записать новый блок <tex>b_2</tex>. Допустим, что мы полностью написали блок <tex>b_1</tex>, а после написали блок <tex>b_2</tex>. В таком случае мы переписали символы в результате алгоритма пересечении двух блоков. Эти символы совпадают, иначе массив <tex>z</tex> был бы некорректным. Поэтому блок <tex>b_1</tex> запишется правильно и полностью. Этот случай мы получаемуже рассмотрели выше.* Рассматриваемый блок <tex>b_1</tex> полностью покрывается блоком <tex>b_2</tex>, который мы уже пишем. Допустим, что мы напишем блок <tex>s[i] \neq ab_1</tex>после того, а как написали блок <tex>b_2</tex>. При корректном массиве <tex>z</tex> символы в пересечении двух блоков совпадут. Тогда мы можем просто рассматривать блок <tex>s[0] = ab_1</tex>)аналогично одному из предыдущих случаев.

Рассмотрим значения <tex>z[i] \ne 0</tex>. В этом случае <tex>s[i]</tex> является началом префикса исходной строки. Назовём подстрокуТаким образом, совпадающую с некоторым префиксом строкимы доказали, блоком. Возможны три положения блока, относительно других блоков. #Он не пересекает другие блоки (но может полностью включать в себя какой-то блок). Тогда что значения массивов <tex>q[i] = z[i]</tex>, потому что наш алгоритм полностью скопирует префикс всей строки.#Рассмотрим случай, когда мы записали часть префикса и прервались для написания нового. Новый блок корректно закончит предыдущий блок (иначе бы массив <tex>z</tex> был бы некорректен, и предыдущий блок будет совпадать с префиксом, тогда <tex>q[i] = z[i]</tex>.#Если блок лежит внутри другого блока, то его массив <tex>q</tex> совпадает с массивом для блока, содержащегося в префиксе строки. Проверяем корректность массива <tex>q</tex> для этого блокасовпадают.