146
правок
Изменения
→Построение строки по Z-функции
Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются, один лежит внутри другого, они пересекаются.
* Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.
* Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый, поэтому не нужно возвращаться к началу малого префикса.* Если префиксы пересекаются, то нам нужно переписать часть префикса, который начинается раньше, и начать писать другой префикс(начало этого префикса запишет конец префикса, начинающегося раньше).
Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.
