3622
правки
Изменения
Нет описания правки
==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#border | бордер ]] длины <tex>k</tex>, то у нее также имеется [[Основные определения, связанные со строками#period | период ]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <tex>\alpha</tex>.
==Свойства периода==
{{Теорема
|author=о кратном периоде
|statement= Если у строки есть период длины <tex>k</tex>, то у нее имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
}}
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> \max(p, q ) > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
* База
*: Истинность утверждения следует из <tex> p = q = r </tex>.
<references/>
== Литература Источники информации ==
* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
* ''Lothaire M. '' Algebraic Combinatorics on Words — {{---}} Cambridge University Press, 2002. — {{---}} с. 272. — {{---}} ISBN 0-521-81220-8
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]