Период и бордер, их связь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связь периода и бордера)
(Связь периода и бордера)
Строка 1: Строка 1:
 
==Связь периода и бордера==
 
==Связь периода и бордера==
 
{{Теорема
 
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками|бордер]] длины <tex>|k|</tex>, то у нее есть [[Основные определения, связанные со строками|период]] длины <tex>|n - k|</tex>.
+
|statement= Если у строки длины <tex>|n|</tex> есть [[Основные определения, связанные со строками|бордер]] длины <tex>|k|</tex>, то у нее есть [[Основные определения, связанные со строками|период]] длины <tex>|n - k|</tex>.
 
|proof=
 
|proof=
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/>
+
Напишем формально определения бордера длины <tex>|k|</tex> строки <tex>\alpha</tex>:<br/>
 
<tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/>
 
<tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/>
 
Сделаем замену <tex>x = n - k</tex>:<br/>
 
Сделаем замену <tex>x = n - k</tex>:<br/>

Версия 11:32, 8 апреля 2012

Связь периода и бордера

Теорема:
Если у строки длины [math]|n|[/math] есть бордер длины [math]|k|[/math], то у нее есть период длины [math]|n - k|[/math].
Доказательство:
[math]\triangleright[/math]

Напишем формально определения бордера длины [math]|k|[/math] строки [math]\alpha[/math]:
[math]\forall i = 1 \ldots k[/math], [math]\alpha [i] = \alpha[i + (n - k)][/math].
Сделаем замену [math]x = n - k[/math]:
[math]\forall i = 1 \ldots n - x[/math], [math]\alpha [i] = \alpha[i + x][/math].

Получили определение периода длины [math]x[/math]. Но [math]x = n - k[/math], значит у строки [math]\alpha[/math] есть период длины [math]|n - k|[/math].
[math]\triangleleft[/math]

Свойства периода

Теорема:
Если у строки есть период длины [math]|k|[/math], то у нее есть период длины [math]|k \cdot x|[/math], где [math] x \in N[/math].
Доказательство:
[math]\triangleright[/math]

Пусть длина строки равна [math]n[/math].
Доказательство будем вести по индукции по числу [math]x[/math].
Для [math] x = 1 [/math] утверждение очевидно.
Пусть верно для [math]x = m[/math]. Докажем, что верно для [math]x = m + 1[/math].
Из определения периода имеем, что
для [math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + k][/math], а из предположения индукции, что
для [math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + m \cdot k][/math]
Значит получаем, что
[math]\forall i = 1 \ldots n - k[/math] [math]\alpha [i] = \alpha [i + m \cdot k] = \alpha[i + m \cdot k + k][/math], следовательно
для [math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + (m + 1) \cdot k][/math].
Значит у строки есть период длины [math] |(m + 1) \cdot k|[/math].

Утверждение доказано.
[math]\triangleleft[/math]
Теорема:
Если у строки есть периоды длины [math]|p|[/math] и [math]|q|[/math], то НОД[math](p, q)[/math] также является периодом этой строки.
Доказательство:
[math]\triangleright[/math]

Пусть [math] p \gt q [/math], тогда
для [math]\forall i = 1 \ldots n - p[/math], [math]\alpha [i] = \alpha[i + p] = \alpha[i + q][/math].
Значит для [math]\forall i = q \ldots n - p[/math], [math]\alpha [i + q] = \alpha[i + p][/math]
Сделаем замену [math]j = i + q[/math] и получим, что для [math]\forall j = 1 \ldots n - (p - q)[/math], [math]\alpha [j] = \alpha[j + (p - q)][/math]
Получили новый период длины [math]|p - q|[/math]. Пусть теперь [math]p = max(p - q, q)[/math], а [math]q = min(p - q, q)[/math].
Будем повторять алгоритм сначала, пока [math]p \lt \gt q[/math].

Видно, что представленный алгоритм - это алгоритм Евклида. Значит при его завершении получим, что последний найденный период равен НОД[math](p, q)[/math].
[math]\triangleleft[/math]