Изменения

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

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

15 байт добавлено, 16:04, 25 апреля 2012
Свойства периода
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,<br/>
а из <b>предположения</b> индукции, что<br/>
<tex>\forall i = 1 \ldots n - kkm</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/>
Значит получаем, что<br/>
<tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,<br/>
следовательно<br/>
для <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>.<br/>
Значит у строки есть <b>период длины</b> <tex>(m + 1)k</tex>.<br/></li>
</ol>
148
правок

Навигация