172
правки
Изменения
→Алгоритм поиска
1) <tex>i > right</tex>:<br>
Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.
Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>. В данном случае будет определено корректное значение <tex>Z[i]</tex> в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.
<br>
2) <tex>i \le right</tex>:<br>
Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто наивно пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>. Корректность в таком случае также гарантированна. Иначе мы уже знаем верное значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.<br>
[[Файл:z-func.png]]
