Изменения

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

Период и бордер, их связь

19 байт добавлено, 14:08, 21 апреля 2012
→‎Связь периода и бордера
Пусть дана <b>строка <tex>\alpha</tex></b>.
Напишем формально определения <b>бордера длины <tex>|k|</tex></b> строки <tex>\alpha</tex>:<br/>
<ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul>Сделаем <b>замену </b> <tex>x = n - k</tex>:<br/> <ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>. </ul>
Получили определение <b>периода длины <tex>x</tex></b>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть <b>период длины <tex>|n - k|</tex></b>.
}}
Dimitrova
148
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/20950»

Навигация