308
правок
Изменения
м
Нет описания правки
{{Определение
|definition =
Число <tex>p</tex> называется '''периодом''' строки <tex>\alpha</tex>, если <tex>\quad \forall i = 1 \ldots n - p</tex> <tex>: \quad \alpha [i] = \alpha[i + p]</tex>.
|id=border
}}
==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Период_и_бордер,_их_связь#Определения|бордер]] длины <tex>k</tex>, то у нее есть [[Период_и_бордер,_их_связь#Определения|также имеется период]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <tex>\alpha</tex>.
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:
: <tex>\forall i = 1 \ldots k</tex>, <tex>: \ \alpha [i] = \alpha[i + (n - k)]</tex>.
Сделаем замену <tex>x = n - k</tex>:
: <tex>\forall i = 1 \ldots n - x</tex>, <tex>: \ \alpha [i] = \alpha[i + x]</tex>.
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
}}
==Теорема о кратном периоде==
{{Теорема
|statement= Если у строки есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>k</tex>, то у нее есть имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем, что верно для <tex>x = m + 1</tex>.
*: Из определения периода имеем
*:: <tex>\forall i = 1 \ldots n - k</tex>, <tex>: \ \alpha [i] = \alpha[i + k]</tex>,
*: а из предположения индукции
*:: <tex>\forall i = 1 \ldots n - km</tex>, <tex>: \ \alpha [i] = \alpha[i + mk]</tex>.
*: Значит получаем, что
*:: <tex>\forall i = 1 \ldots n - km - k</tex>, <tex>: \ \alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,
*: следовательно
*:: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>: \ \alpha [i] = \alpha[i + k(m + 1)]</tex>.
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
Требуется показать что <tex> s_i = s_{i+p-q} \ \ (i = 1,\dots,n-p\ , \ n=|s|) </tex>
Поскольку <tex> s </tex> имеет период <tex> p </tex>, выполнено <tex> s_i = s_{i+p} </tex>
*: Пусть <tex> w = uv </tex>, где <tex> |u| = q </tex>.
*: По '''лемме 1''' <tex> v </tex> имеет период <tex> p - q </tex>, также <tex> v </tex> имеет период <tex> q </tex> как подстрока <tex> w </tex>. Теперь рассмотрим длину <tex> v </tex>:
*: <tex> |v| = |w| - q \geqslant (p + q - r) - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) </tex>.
*: Тогда по предположению индукции получаем, что <tex> v </tex> также имеет период <tex> \gcd(p-q, q)</tex>. Поскольку <tex> \gcd(p-q, q) = \gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.
*: Ещё заметим, что <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| = |w| - q \geqslant (p + - q - r) - q \geqslant q + (p - q) - r \geqslant q </tex>, тогда по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
}}
