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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства периода)
(Свойства периода)
Строка 32: Строка 32:
 
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
 
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
 
|proof=
 
|proof=
Пусть строка равна <tex> \alpha </tex>, а <tex> p > q </tex>, тогда<br/>  
+
Пусть строка равна <tex> \alpha </tex>.<br/>
для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>
+
Доказательство будем вести по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
 +
(p + 1, 1), &  q = p.\end{cases}</tex><br/>
 +
Для <tex> (1, 1) </tex> утверждение очевидно.<br/>
 +
Пусть верно для <tex>(p, q) - 1 < (p, q)</tex>.<br/>
 +
Докажем, что верно для <tex>(p, q)</tex>.
 +
Для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>
 
Значит для <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/>
 
Значит для <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/>
 
Сделаем замену <tex>j = i + q</tex> и получим, что
 
Сделаем замену <tex>j = i + q</tex> и получим, что
 
для <tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex><br/>
 
для <tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex><br/>
Получили новый период длины <tex>|p - q|</tex>. Пусть теперь <tex>p = max(p - q, q)</tex>, а <tex>q = min(p - q, q)</tex>.<br/>
+
Получили новый период длины <tex>|p - q|</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex> <tex>=</tex> НОД<tex>(p, q)</tex>. Следовательно утверждение доказано.
Будем повторять алгоритм сначала, пока <tex>p <> q</tex>.
 
Видно, что представленный алгоритм - это алгоритм Евклида. Значит при его завершении получим, что последний найденный период равен НОД<tex>(p, q)</tex>.
 
 
}}
 
}}
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 18:35, 20 апреля 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 = 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 + mk][/math]
Значит получаем, что
[math]\forall i = 1 \ldots n - k[/math], [math]\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k][/math], следовательно
для [math]\forall i = 1 \ldots n - k[/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) - 1 \lt (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]