148
правок
Изменения
→Свойства периода
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|kx|</tex>, где <tex> x \in N</tex>.
|proof=
Пусть <b>длина </b> строки равна <tex>n</tex>, сама <b>строка </b> {{---}} <tex> \alpha </tex>.<br/>Доказательство будем вести по <b>индукции по числу </b> <tex>x</tex>.<br/><ol><li>Для <tex> x = 1 </tex> утверждение очевидно.<br/li><li>Пусть верно для <tex>x = m</tex>. </li><li>Докажем, что верно для <tex>x = m + 1</tex>.<br/>Из <b>определения периода </b> имеем, что<br/>для <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 - k</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/>
Значит получаем, что<br/>
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>, <br/>следовательно<br/> для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>.<br/>Значит у строки есть <b>период длины </b> <tex> |(m + 1)k|</tex>.<br/></li></ol>
Утверждение доказано.
}}
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть <b>строка </b> равна <tex> \alpha </tex>.<br/>Доказательство будем вести <b>по индукции по парам </b> <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
(p + 1, 1), & q = p.\end{cases}</tex><br/>
<ol><li>Для <tex> (1, 1) </tex> утверждение очевидно.<br/li><li>Пусть верно для всех <b>пар меньших </b> <tex>(p, q)</tex>.<br/li><li>Докажем, что верно для <tex>(p, q)</tex>. <br/> Из <b>определения периода</b>:<br/>Для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>Значит для <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/>Сделаем замену <tex>j = i + q</tex> и получим, что<br/>для <tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex><br/>Получили новый <b>период длины </b> <tex>|p - q|</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex> <tex>=</tex> НОД<tex>(p, q)</tex>. </li></ol>Следовательно утверждение доказано.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
