308
правок
Изменения
м
→Свойства периода
==Свойства периода==
==Теорема о кратном периоде==
{{Теорема
|statement= Если у строки есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>k</tex>, то у нее есть период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.<br/> Доказательство будем вести по индукции по числу <tex>x</tex>.<br/><ol><li>* База*: Для <tex> x = 1 </tex> утверждение очевидно.</li><li>* Переход*: Пусть верно для <tex>x \leqslant m</tex>.</li><li>Докажем, что верно для <tex>x = m + 1</tex>.<br/>*: Из определения периода имеем, что<br/><ul>*: <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,</ul>*: а из предположения индукции, что<br/><ul>*: <tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex></ul>*: Значит получаем, что<br/><ul>*: <tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,</ul>*: следовательно<br/><ul>для *: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.</ul>*: Значит у строки есть период длины <tex>k(m + 1)</tex>.<br/></li></ol>
Утверждение доказано.
}}
==Теорема о НОД периодов==
Перед доказательством следующей теоремы докажем пару интуитивно понятных утверждений.
{{Лемма
|about=2
|statement= Пусть строка <tex> w </tex> имеет период <tex> q </tex>, и существует <tex> v </tex> подстрока <tex> w </tex> такая, что <tex> |v| \geqslant q </tex> и <tex> v </tex> имеет период <tex> r </tex>, где <tex> q </tex> делится на <tex dpi=90>\,\vdots\, </tex> <tex> r </tex>. Тогда <tex> w </tex> имеет период <tex> r </tex>.
|proof= Пусть <tex> w = s_1 \dots s_n,\ v = s_h \dots s_k </tex>, где <tex> 1 \leqslant h < k \leqslant n </tex>.
Заметим, что поскольку <tex> |v| \geqslant q </tex>, то отрезок <tex> [h, k] </tex> содержит ровно <tex> q </tex> целых чисел, так что найдутся <tex> i',\ j' \in [h, k] </tex> такие, что <tex> i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
Так как <tex> q </tex> делится на <tex dpi=90>\,\vdots\, </tex> <tex> r </tex> , можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex>.
Помимо того <tex> i \equiv j \pmod r </tex>, тогда верно и <tex> i' \equiv j' \pmod r </tex>.
