Материал из Викиконспекты
|
|
| Строка 3: |
Строка 3: |
| | |statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>n - k</tex>. | | |statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>n - k</tex>. |
| | |proof= | | |proof= |
| − | Пусть дана <b>строка <tex>\alpha</tex></b>. | + | Пусть дана строка <tex>\alpha</tex>.<br/> |
| − | Напишем формально определения <b>бордера длины <tex>k</tex></b> строки <tex>\alpha</tex>:<br/> | + | Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/> |
| | <ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul> | | <ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul> |
| − | Сделаем <b>замену</b> <tex>x = n - k</tex>:<br/> | + | Сделаем замену <tex>x = n - k</tex>:<br/> |
| | <ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul> | | <ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul> |
| − | Получили определение <b>периода длины <tex>x</tex></b>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть <b>период длины <tex>n - k</tex></b>. | + | Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>. |
| | }} | | }} |
| | | | |
Версия 16:10, 25 апреля 2012
Связь периода и бордера
| Теорема: |
Если у строки длины [math]n[/math] есть бордер длины [math]k[/math], то у нее есть период длины [math]n - k[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть дана строка [math]\alpha[/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]kx[/math], где [math] x \in N[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть длина строки равна [math]n[/math], сама строка — [math]\alpha[/math].
Доказательство будем вести по индукции по числу [math]x[/math].
- Для [math] x = 1 [/math] утверждение очевидно.
- Пусть верно для [math]x \leqslant 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 - km[/math], [math]\alpha [i] = \alpha[i + mk][/math]
Значит получаем, что
[math]\forall i = 1 \ldots n - k(m + 1)[/math], [math]\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k][/math],
следовательно
для [math]\forall i = 1 \ldots n - k(m + 1)[/math], [math]\alpha [i] = \alpha[i + (m + 1)k][/math].
Значит у строки есть период длины [math](m + 1)k[/math].
Утверждение доказано. |
| [math]\triangleleft[/math] |
| Теорема: |
Если у строки есть периоды длины [math]p[/math] и [math]q[/math], то НОД[math](p, q)[/math] также является периодом этой строки. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть строка равна [math] \alpha [/math].
Доказательство будем вести по индукции по парам [math](p, q)[/math], где [math] p \geqslant q [/math], а [math](p, q) + 1 = \begin{cases} (p, q + 1), & q \lt p;\\
(p + 1, 1), & q = p.\end{cases}[/math]
- Для [math] (1, 1) [/math] утверждение очевидно.
- Пусть верно для всех пар меньших [math](p, q)[/math].
- Докажем, что верно для [math](p, 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 - q, q)[/math] — период строки, но НОД[math](p - q, q)[/math][math]=[/math]НОД[math](p, q)[/math].
Следовательно утверждение доказано. |
| [math]\triangleleft[/math] |
