148
правок
Изменения
→Свойства периода
==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|k \cdot x|</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>.<br/>
Пусть верно для <tex>x = m</tex>. Докажем, что верно для <tex>x = m + 1</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 k]</tex><br/>
Значит получаем, что<br/>
<tex>\forall i = 1 \ldots n - k</tex> <tex>\alpha [i] = \alpha [i + m \cdot k] = \alpha[i + m \cdot k + 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/>
Утверждение доказано.
{{Теорема
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть <tex> p > q </tex>, тогда<br/>
для <tex>\forall i = 1 \ldots n - qp</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>Значит для <tex>\forall i = 1 q \ldots n - (p - q)</tex>, <tex>\alpha [i+ q] = \alpha[i + (p - q)]</tex><br/>Теперь, следуя алгоритму Евклида, если Сделаем замену <tex> j = i + q </tex> и получим, чтодля <tex>\forall j = 1 \ldots n - (p - q )</tex>, получим <tex>\alpha [ij] = \alpha[i j + (q - (p - q))]</tex>,<br/>иначе Получили новый период длины <tex>\alpha [i] = \alpha[i + (|p - q) - q]|</tex>.Пусть теперь <tex>p = max(p - q, q)<br/tex>Будем выполнять такие действия, пока не получим НОДа <tex>q = min(p- q, q)</tex>. Это будет выполнятся для <br/>Будем повторять алгоритм сначала, пока <tex>\forall i p <> q</tex>. Следовательно будет Видно, что представленный алгоритм - это алгоритм Евклида. Значит при его завершении получим, что последний найденный период длины равен НОД<tex>(p, q)</tex>.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
