165
правок
Изменения
→Основные положения
{{Утверждение
|statement=
Строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условию 1.
Из того, что выполняется условие 1 следует, что один из суффиксов хотя бы на <tex>|s|</tex> длиннее другого. При этом они оба начинаются со строки <tex>s</tex>. Поэтому строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь.
}}
{{Утверждение
|statement=
Если строка <tex>s</tex> является максимальной входящей в <tex>t</tex> дважды, то она удовлетворяет условию 2.
|proof=
Пусть это не так и <tex>|s| < \min\limits_{k=i'\dots j'}lcp[k]</tex> (больше она быть не может). Тогда получим, что |s| меньше, чем длина наибольшего общего префикса суффиксов <tex>i</tex> и <tex>j</tex>, чего быть не может по построению <tex>i</tex> и <tex>j</tex>.
}}
