Zi(S)
Для данной строки S и позиции
i > 1 определим Zi(S) как длину наибольшей подстроки S, которая начинается в
i и совпадает с префиксом S.
Z-блок
Для любой позиции i > 1, в
которой Zi > 0, определим Z-блок в i как интервал, начинающийся в i и
кончающийся в позиции i + Zi - 1.
Определение. Для любого i
> 1 пусть r, — крайний правый конец Z-блоков, начинающихся не позднее
позиции i. По-другому r, можно определить как наибольшее значение j +Zj - 1 по
всем 1 < j <= i, для которых Zi >0
Обозначим значение j, на
котором достигается этот максимум, через li. Таким образом, li — это позиция
левого конца Z-блока, кончающегося в ri. В случае если таких Z-блоков,
кончающихся в ri, больше одного, в качестве li берется левый конец любого из
них.
Z-алгоритм
При заданных Zi для всех l
< i <= k - 1 и текущих значениях r и l величина Zk
и изменения для r и l
вычисляются следующим образом:
begin
1. Если k > r, то найти Zk
непосредственным сравнением до несовпадения подстрок, начинающихся с позиции
Лис позиции 1. Длина совпадающей части и дает Zk. Если Zk > 0, положить r =
k +Zk - 1 и l = k.
2. Если k<=r, то позиция к
находится в Z-блоке, и следовательно, S(k) содержится в подстроке S[l..r]
(назовем ее а), такой что l > 1 и а совпадает с префиксом S. Поэтому символ
S(k) стоит и в позиции ki = k - l + 1.
По тем же причинам подстрока
S[k..r] (назовем ее B) должна совпадать с подстрокой S[ki..Zl]. Отсюда следует,
что подстрока, начинающаяся с позиции k, должна совпадать по меньшей мере с
префиксом S длины min{Zk |B|} = r - k + 1
Рассмотрим два отдельных
случая, в зависимости от того, на чем достигается этот минимум.
2а. Если Zki < |B|, то Zk
= Zki и r,l не изменяются (рис. 1.4).
2Ь. Если Zki> = |B|, то
вся подстрока 5[k..г] должна быть префиксом S и Zk>=|B| = r - k+ 1. Однако
Zk может быть больше, чем B, так что нужно сравнить до несовпадения символы,
начиная с позиции r + 1, с символами, начиная с позиции |B| + 1. Пусть
несовпадение произошло на символе q >= r + 1. Тогда Zk полагается равным q -
к, r = q - 1
и l = k
|