148
правок
Изменения
Новая страница: «==Связь периода и бордера== {{Теорема |statement= Если у строки длины <tex>n</tex> есть [[Основные опре...»
==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками|период]] длины <tex>(n - k)</tex>.
|proof=
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</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>\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>n</tex> есть [[Основные определения, связанные со строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками|период]] длины <tex>(n - k)</tex>.
|proof=
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</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>\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>.
}}
