148
правок
Изменения
Нет описания правки
==Определения==
{{Определение
|definition =
Строка <tex>\alpha</tex> называется '''бордером''' строки <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом <tex>\beta</tex>.
|id=border
}}
{{Определение
|definition =
Число <tex>p</tex> называется '''периодом''' строки <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
|id=border
}}
==Связь периода и бордера==
{{Теорема
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть периоды длины <tex>p</tex> и <tex>q</tex>, где <tex>p + q \leqslant n</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Для удобства доказательства допишем перед строкой её копию и будем нумеровать символы новой строки не с <tex>1</tex> до <tex>2n</tex>, а с <tex>-n + 1</tex> до <tex>n</tex>. Назовём полученную строку <tex>\alpha</tex>.<br/>
