Изменения

|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строкамиborder |бордер]] длины <tex>k</tex>, то у нее есть также имеется [[Основные определения, связанные со строками#Отношения между строкамиperiod |период]] длины <tex>n - k</tex>.

Пусть дана строка <tex>\alpha</tex>.<br/> Напишем формально определения определение бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/><ul>: <tex>\forall i = 1 \ldots k</tex>, <tex>: \ \alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul>Сделаем замену <tex>x = n - k</tex>:<br/><ul>: <tex>\forall i = 1 \ldots n - x</tex>, <tex>: \ \alpha [i] = \alpha[i + x]</tex>.</ul>

|author=о кратном периоде|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>k</tex>, то у нее есть имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.

Пусть длина строки равна <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(m + 1)</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)k]</tex>.</ul>*: Значит у строки есть период длины <tex>k(m + 1)k</tex>.<br/></li></ol>

|statement= Если у строки <tex>w</tex> есть периоды длины <tex>p</tex> и <tex>q</tex>, где <tex> |w| \geqslant p + q - \gcd(p, q) </tex>, то НОД<tex>\gcd(p, q)</tex> также является периодом этой строки.|author=Фин и Вильф|proof=Пусть строка равна Обозначим <tex> r = \alpha gcd(p, q) </tex>.<br/>Доказательство будем вести индукцией по индукции по парам <tex>n = (p, + q)/ r </tex>. В случае <tex> p = q </tex>видим что <tex> n = 2 </tex>, что соответствует базе, где в то время как при <tex> p \geqslant ne q </tex>, а выполнено <tex>\max(p, q) + 1 = > \begin{cases} gcd(p, q + 1)</tex>, & q так что <tex> n > 2 < p;\\/tex>.* База(*: Истинность утверждения следует из <tex> p + 1, 1), & = q = pr </tex>.\end{cases}* Переход*: В силу того, что </tex>p \ne q <br/tex>, без ограничения общности будем считать <oltex>q <li>Для p </tex> (1вообще говоря, 1) исходя из свойств НОД можно дать более строгую оценку: </tex> утверждение очевидно.p - q \geqslant r </litex>, чем мы позже воспользуемся).*: Пусть <litex>Пусть верно для всех пар меньших w = uv </tex>(p, где <tex> |u| = q)</tex>.*: По '''лемме 1''' </litex>v <li/tex>Докажем, что верно для имеет период <tex>(p, - q)</tex>., также <tex> v <br/tex> Из определения периода:имеет период <tex> q <br/tex>как подстрока <tex> w <ul/tex>. Теперь рассмотрим длину <tex>\forall i = 1 \ldots n - pv </tex>, : *: <tex>\alpha [i] |v| = |w| - q \alpha[i geqslant (p + q - r) - q \geqslant (p] - q) + q - r = (p - q) + q - \alpha[i + gcd(p - q, q]) </tex>.*: Ещё заметим, что для периодов </ultex>Значит p - q,\ q <ul/tex>будет меньшее <tex>\forall i = q \ldots n - p</tex>, нежели чем для <tex>p,\alpha [i + q] = \alpha[i + p]</tex></ul>Сделаем замену , поскольку <tex>j \gcd(p-q, q) = i + \gcd(p, q) </tex> и получим, что. А тогда по предположению индукции заключаем: <br/tex>v <ul/tex>имеет период <tex>\forall j = 1 \ldots n - gcd(p - q, q)</tex>, . Учитывая <tex>\alpha [j] gcd(p-q, q) = \alpha[j + gcd(p - , q)]= r </tex>, можем сказать что <tex> v </ultex>Получили новый имеет период длины <tex>p - qr </tex>. Из предположения известно*: Как уже упоминалось, что НОД<tex>(p - q, q)\geqslant r </tex> {{---}} период строки, но НОДпоэтому <tex>|v| \geqslant (p - q, ) + q - r \geqslant q)</tex>, в следствие чего по '''лемме 2''' <tex>=w </tex>НОДимеет период <tex>(p, q)r </tex>.</li></ol>Следовательно утверждение доказано.