Изменения

|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</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>

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

* [[Основные определения, связанные со строками]] == Примечания ==<references/> == Источники информации ==* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]* ''Lothaire M.'' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8