Изменения

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

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

312 байт добавлено, 14:48, 4 мая 2012
Свойства периода
|statement= Если у строки есть периоды длины <tex>p</tex> и <tex>q</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть строка равна <tex> \alpha </tex>. Для удобства доказательства, не меняя общности, допишем перед строкой её копию и будем нумеровать символы новой строки не с <tex>1</tex> до <tex>2n</tex>, а с <tex>-n + 1</tex> до <tex>n</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/>
<li>Докажем, что верно для <tex>(p, q)</tex>.<br/>
Из определения периода:<br/>
<ul><tex>\forall i = -n + 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.</ul>Значит <ul><tex>\forall i = 1 - q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex></ul>
Сделаем замену <tex>j = i + q</tex> и получим, что<br/>
<ul><tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex></ul>
Анонимный участник

Навигация