Изменения

Перейти к: навигация, поиск

Суффиксный массив

1068 байт добавлено, 17:53, 5 июня 2016
Основные положения
Если для каких-нибудь суффиксов <tex>i</tex> и <tex>j</tex> соответствующая им строка <tex>s</tex> удовлетворяет условиям 1 и 2, то она входит в <tex>t</tex> дважды и не пересекаясь.
|proof=
proofИз того, что выполняется условие 1 следует, что один из суффиксов хотя бы на <tex>|s|</tex> длиннее другого. При этом они оба начинаются со строки <tex>s</tex>. Поэтому строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь. Условию 2 же строка удовлетворяет по построению.Ч.т.д.
}}
Если строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то соответствующие ей суффиксы <tex>i</tex> и <tex>j</tex> удовлетворяют условиям 1 и 2.
|proof=
proofЕсли строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на <tex>|s|</tex> длиннее другого. Т.е. условие 1 выполнено. Условие 2 выполняется, т.к. иначе наибольший общий префикс <tex>i</tex> и <tex>j</tex> был бы меньше <tex>|s|</tex>, чего не может быть по построению <tex>s</tex>. Т.е. условие 2 тоже выполнено.Ч.т.д.
}}
165
правок

Навигация