308
правок
Изменения
м
Ограничение <tex> |w| \geqslant p + q - \gcd(p, q) </tex> существенно. Например строка <tex> w = abaababaaba </tex> имеет периоды <tex> 5 </tex> и <tex> 8 </tex>, её длина <tex> 11 < 5 + 8 - 1 </tex>, и периода = Примечания ==<texreferences> 1 </texreferences> у неё нет.
Нет описания правки
|statement= Если у строки длины <tex>n</tex> есть [[Период_и_бордер,_их_связь#Определения|бордер]] длины <tex>k</tex>, то у нее есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <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>Сделаем замену <tex>x = n - k</tex>:<br/><ul>: <tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
}}
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем, что верно для <tex>x = m + 1</tex>.
*: Из определения периода имеем
*:: <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,
*: а из предположения индукции
*:: <tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex>.
*: Значит получаем, что
*:: <tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,
*: следовательно
*:: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
Заметим, что поскольку <tex> |v| \geqslant q </tex>, то отрезок <tex> [h, k] </tex> содержит ровно <tex> q </tex> целых чисел, так что найдутся <tex> i',\ j' \in [h, k] </tex> такие, что <tex> i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
Так как <tex> q </tex> <tex dpi=90>\,\vdots\, </tex> <tex> r </tex> , можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex> <ref>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойства сравнений]]</ref>.
Помимо того <tex> i \equiv j \pmod r </tex>, тогда верно и <tex> i' \equiv j' \pmod r </tex>.
Теперь воспользуемся тем фактом, что если строка <tex> s </tex> имеет период <tex> r </tex>, то <tex> i \equiv j \pmod r \ \Rightarrow\ s_i = s_j </tex> (действительно, без ограничения общности можем сказать, что <tex> i \leqslant j </tex>, тогда <tex> s_i = s_{i + r}, \ \ s_{i + r} = s_{i + 2r}, \ \ \dots\ , \ s_{j - r} = s_j </tex>).
Поскольку <tex> w </tex> имеет период <tex> q </tex>, имеют место равенства <tex> s_i = s_{i'}\ </tex> и <tex>\ s_j = s_{j'} </tex>. Поскольку <tex> v </tex> имеет период <tex> r </tex>, верно <tex> s_{i'} = s_{j'} </tex>. Тогда и <tex> s_i = s_j </tex>.
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
* База
*: При <tex> n = 1 2 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
* Переход
*: Заметим что теперь <tex> q \ne p </tex> (так как <tex> n \ne 1 > 2 </tex>), поэтому без ограничения общности можем сказать, что <tex> q < p </tex>.
*: Пусть <tex> w = uv </tex>, где <tex> |u| = q </tex>.
*: По '''лемме 1''' <tex> v </tex> имеет период <tex> p - q </tex>, также <tex> v </tex> имеет период <tex> q </tex> как подстрока <tex> w </tex>. Теперь рассмотрим длину <tex> v </tex>:
}}
== См. также ==
* [[Основные определения, связанные со строками]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
