Изменения

Перейти к: навигация, поиск

Период и бордер, их связь

691 байт убрано, 21:39, 15 февраля 2015
Нет описания правки
==Определения==
{{Определение
|definition =
Строка <tex>\alpha</tex> называется '''бордером''' строки <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и [[Основные определения, связанные со строками#Отношения между строками|суффиксом]], и [[Основные определения, связанные со строками#Отношения между строками|префиксом]] <tex>\beta</tex>.
|id=border
}}
 
{{Определение
|definition =
Число <tex>p</tex> называется '''периодом''' строки <tex>\alpha</tex>, если <tex> \quad \forall i = 1 \ldots n - p: \quad \alpha [i] = \alpha[i + p]</tex>.
|id=border
}}
 
==Связь периода и бордера==
{{Теорема
|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=
}}
==Теорема о НОД периодов==
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
== Источники информации ==
* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
* ''Lothaire M. '' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Навигация