Материал из Викиконспекты
Связь периода и бордера
| Теорема: |
Если у строки длины [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 * x)[/math], где [math] x \in N[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть Длина строки равна [math]n[/math]. Тогда из определения периода имеем, что
[math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha[i + k][/math].
Это вернео для всех таких [math]i[/math], значит получаем
[math]\alpha [i] = \alpha[i + k][/math].
[math]\alpha [i + k] = \alpha[i + 2* k][/math].
[math]\alpha [i + 2 * k] = \alpha[i + 3 * k][/math].
[math] \ldots [/math]
[math]\alpha [i + (x - 1) * k] = \alpha[i + x * k][/math].
Следовательно для [math]\forall i = 1 \ldots n - x * k[/math], [math]\alpha [i] = \alpha[i + x *k][/math].
Значит у строки есть период длины [math](k * x)[/math]. |
| [math]\triangleleft[/math] |
