148
правок
Изменения
→Связь периода и бордера
|proof=
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/>
<tex>\forall i = 1 \ldots k</tex> , <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/>
Сделаем замену <tex>x = n - k</tex>:<br/>
<tex>\forall i = 1 \ldots n - x</tex> , <tex>\alpha [i] = \alpha[i + x]</tex>.
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>(n - k)</tex>.
}}
==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>(k * x)</tex>, где <tex> x \in N</tex>.
|proof=
Пусть Длина строки равна <tex>n</tex>. Тогда из определения периода имеем, что<br/>
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
Это вернео для всех таких <tex>i</tex>, значит получаем <br/>
<tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
<tex>\alpha [i + k] = \alpha[i + 2* k]</tex>.<br/>
<tex>\alpha [i + 2 * k] = \alpha[i + 3 * k]</tex>.<br/>
<tex> \ldots </tex><br/>
<tex>\alpha [i + (x - 1) * k] = \alpha[i + x * k]</tex>.<br/>
Следовательно для <tex>\forall i = 1 \ldots n - x * k</tex>, <tex>\alpha [i] = \alpha[i + x *k]</tex>.<br/>
Значит у строки есть период длины <tex>(k * x)</tex>.
}}
