Изменения

Перейти к: навигация, поиск

Период и бордер, их связь

199 байт добавлено, 18:35, 20 апреля 2012
Свойства периода
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть строка равна <tex> \alpha </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>j = i + q</tex> и получим, что
для <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)</tex>. Следовательно утверждение доказано.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
148
правок

Навигация