148
правок
Изменения
→Свойства периода
==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|k \cdot xkx|</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>.<br/>
Из определения периода имеем, что<br/>
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>, а из предположения индукции, что<br/>
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + m \cdot kmk]</tex><br/>
Значит получаем, что<br/>
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha [i + m \cdot kmk] = \alpha[i + m \cdot k mk + k]</tex>, следовательно<br/>для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + (m + 1) \cdot k]</tex>.<br/>Значит у строки есть период длины <tex> |(m + 1) \cdot k|</tex>.<br/>
Утверждение доказано.
}}
