308
правок
Изменения
м
→Свойства периода
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
Требуется показать что <tex> s_i = s_{i+p-q} \ \ (i = 1,\dots,n-p; \ , \ n=|s|) </tex>
Поскольку <tex> s </tex> имеет период <tex> p </tex>, выполнено <tex> s_i = s_{i+p} </tex>
{{Лемма
|about=2
|statement= Пусть строка <tex> w </tex> имеет период <tex> q </tex>, и существует <tex> v </tex> подстрока <tex> w </tex> такая, что <tex> |v| \geqslant q </tex> и <tex> v </tex> имеет период <tex> r </tex>, где <tex> q </tex> делится на <tex> r | q </tex>. Тогда <tex> w </tex> имеет период <tex> r </tex>.
|proof= Пусть <tex> w = s_1 \dots s_n,\ v = s_h \dots s_k </tex>, где <tex> 1 \leqslant h < k \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> r </tex>, можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex>.
Помимо того <tex> i \equiv j \pmod r </tex>, тогда верно и <tex> i' \equiv j' \pmod r </tex>.
{{Теорема
|statement= Если у строки <tex>w</tex> есть периоды <tex>p</tex> и <tex>q</tex>, где <tex> |w| \geqslant p + q - GCD\gcd(p, q) </tex>, то НОД<tex>\gcd(p, q)</tex> также является периодом этой строки.
|author=Фин и Вильф
|proof=Обозначим <tex> r = GCD\gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
* База
*: При <tex> n = 1 </tex> видно, что <tex> p = q = r </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) + q - r = (p - q) + q - GCD\gcd(p - q, q) </tex>.*: Тогда по предположению индукции получаем, что <tex> v </tex> также имеет период <tex> GCD(p-q, q)</tex>. Поскольку <tex> GCD\gcd(p-q, q) = GCD\gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.*: Ещё заметим, что <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| = |w| - q \geqslant (p + q - r) - q) \geqslant q + (p - q ) - r \geqslant q </tex>, тогда по лемме 2 <tex> w </tex> имеет период <tex> r </tex>.
}}
Ограничение <tex> |w| \geqslant p + q - GCD\gcd(p, q) </tex> существенно. Например строка <tex> w = abaababaaba </tex> имеет периоды <tex> 5 </tex> и <tex> 8 </tex>, её длина <tex> 11 < 5 + 8 - 1 </tex>, и периода <tex> 1 </tex> у неё нет.
== См. также ==
