308
правок
Изменения
Переделывание доказательства про НОД
Утверждение доказано.
}}
{{Лемма
|about=1
|statement= Пусть строка <tex> w </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> p < q \leqslant |w| </tex>. Тогда суффикс и префикс <tex> w </tex> длины <tex> |w| - q </tex> имеют период <tex> p - q </tex>.
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
Требуется показать что <tex> s_i = s_{i+p-q} \ \ (i = 1,\dots,n-p) </tex>
Поскольку <tex> w </tex> имеет период <tex> p </tex>, выполнено <tex> s_i = s_{i+p} </tex>
Также <tex> w </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>
}}
{{Лемма
|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> 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> a_i = a_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' </tex> и <tex> j' </tex> такие, что <tex> i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>.
}}
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть периоды <tex>p</tex> и <tex>q</tex>, где <tex>p + q - НОД(p, q) \leqslant n</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.|author=Фин и Вильф
|proof=
}}
