308
правок
Изменения
м
Поскольку Исходя из того, что <tex> s </tex> имеет период <tex> p </tex>, выполнено <tex> s_i = s_{i+p} </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>.
Нет описания правки
Пусть дана строка <tex>\alpha</tex>.
Напишем формально определения определение бордера длины <tex>k</tex> строки <tex>\alpha</tex>:
: <tex>\forall i = 1 \ldots k: \ \alpha [i] = \alpha[i + (n - k)]</tex>
*: Для <tex> x = 1 </tex> утверждение очевидно.
* Переход
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем, что верно то же для <tex>x = m + 1</tex>.
*: Из определения периода имеем
*:: <tex>\forall i = 1 \ldots n - k: \ \alpha [i] = \alpha[i + k]</tex>
*: а из предположения индукции
*:: <tex>\forall i = 1 \ldots n - km: \ \alpha [i] = \alpha[i + mk]</tex>
*: Значит С учётом этого получаем, что
*:: <tex>\forall i = 1 \ldots n - km - k: \ \alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>
*: следовательно
==Теорема о НОД периодов==
Перед доказательством следующей теоремы докажем пару интуитивно понятных паонятных утверждений.
{{Лемма
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
Требуется показать что : <tex> s_i = s_{i+p-q} \ \ (i = 1 \dots n-p\ , \ n=|s|) </tex>
Также <tex> s </tex> имеет период <tex> q </tex> и из ограничений на <tex> i </tex> верно <tex> 1 \leqslant i + p - q \leqslant n - q </tex>, поэтому <tex> s_{i+p-q} = s_{i+p} </tex>
}}
Требуется показать: <tex> s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </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>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойство сравнений (№8)]]</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> n = 2 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
* Переход
*: Заметим что теперь <tex> q \ne p </tex> (так как <tex> n > 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>:
*: <tex> |v| = |w| - q \geqslant (p + q - r) - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) </tex>.
*: Тогда Таким образом по предположению индукции получаем, что <tex> v </tex> также имеет период <tex> \gcd(p-q, q)</tex>. Поскольку Учитывая <tex> \gcd(p-q, q) = \gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.*: Ещё заметим, что одно наблюдение: <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| \geqslant (p - q) + q - r \geqslant q </tex>, тогда в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
}}
