Изменения

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

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

4445 байт добавлено, 21:39, 15 февраля 2015
Нет описания правки
==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строкамиborder |бордер]] длины <tex>k</tex>, то у нее есть также имеется [[Основные определения, связанные со строками#Отношения между строкамиperiod |период]] длины <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>.
}}
==Свойства периода==
{{Теорема
|author=о кратном периоде|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>k</tex>, то у нее есть имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть <b>длина</b> строки равна <tex>n</tex>, сама <b>строка</b> {{---}} <tex>\alpha</tex>.<br/> Доказательство будем вести по <b>индукции индукцией по числу</b> <tex>x</tex>.<br/><ol><li>* База*: Для <tex> x = 1 </tex> утверждение очевидно.</li><li>* Переход*: Пусть верно для <tex>x \leqslant m</tex>.</li><li>Докажем, что верно то же для <tex>x = m + 1</tex>.<br/>*: Из <b>определения периода</b> имеем, что<br/> *:: <tex>\forall i = 1 \ldots n - k</tex>, <tex>: \ \alpha [i] = \alpha[i + k]</tex>,<br/>*: а из <b>предположения</b> индукции, что<br/> *:: <tex>\forall i = 1 \ldots n - km</tex>, <tex>: \ \alpha [i] = \alpha[i + mk]</tex><br/>Значит *: С учётом этого получаем, что<br/> *:: <tex>\forall i = 1 \ldots n - km - k(m + 1)</tex>, <tex>: \ \alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,<br/>*: следовательно<br/> для *:: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>: \ \alpha [i] = \alpha[i + k(m + 1)k]</tex>.<br/>*: Значит у строки есть <b>период длины</b> <tex>k(m + 1)k</tex>.<br/></li></ol>
Утверждение доказано.
}}
 
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
 
{{Лемма
|about=1
|statement= Пусть строка <tex> s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> q < p \leqslant |s| </tex>. Тогда суффикс и префикс <tex> s </tex> длины <tex> |s| - q </tex> имеют период <tex> p - q </tex>.
|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>
Также <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>
}}
 
{{Лемма
|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 dpi=90>\,\vdots\, </tex> <tex> r </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> s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </tex>.
 
Зафиксируем <tex> i </tex> и <tex> j </tex>. Заметим, что поскольку <tex> |v| \geqslant q </tex>, отрезок <tex> [h, k] </tex> содержит по меньшей мере <tex> q </tex> целых чисел, так что найдутся <tex> i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q,\ i \ne j </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> 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>.
 
}}
 
{{Теорема
|statement= Если у строки <tex>w</tex> есть периоды длины <tex>p</tex> и <tex>q</tex>, где <tex> |w| \geqslant p + q - \gcd(p, q) </tex>, то НОД<tex>\gcd(p, q)</tex> также является периодом этой строки.|author=Фин и Вильф|proof=Пусть Обозначим <btex>строкаr = \gcd(p, q) </btex> равна . Доказательство будем вести индукцией по <tex> \alpha n = (p + q) / r </tex>.<br/>Доказательство будем вести В случае <btex>по индукции по парамp = q </btex> видим что <tex>(p, q)n = 2 </tex>, где что соответствует базе, в то время как при <tex> p \geqslant ne q </tex>, а выполнено <tex>\max(p, q) + 1 = > \begin{cases} gcd(p, q + 1)</tex>, & q так что <tex> n > 2 < p;\\/tex>.* База(*: Истинность утверждения следует из <tex> p + 1, 1), & = q = pr </tex>.\end{cases}* Переход*: В силу того, что </tex>p \ne q <br/tex>, без ограничения общности будем считать <oltex>q <li>Для p </tex> (1вообще говоря, 1) исходя из свойств НОД можно дать более строгую оценку: </tex> утверждение очевидно.p - q \geqslant r </litex>, чем мы позже воспользуемся).<li>*: Пусть верно для всех <btex>пар меньшихw = uv </btex> , где <tex>(p, |u| = q)</tex>.*: По '''лемме 1''' <tex> v </litex>имеет период <tex> p - q <li/tex>Докажем, что верно для также <tex>(p, q)v </tex>.имеет период <tex> q <br/tex> Из как подстрока <btex>определения периодаw </btex>:. Теперь рассмотрим длину <tex> v <br/tex>: *: <tex>|v| = |w| - q \geqslant (p + q - r) - q \forall i geqslant (p - q) + q - r = 1 (p - q) + q - \ldots n gcd(p - pq, q) </tex>.*: Ещё заметим, что для периодов <tex>\alpha [i] = \alpha[i + p] = - q,\alpha[i + q]</tex>.будет меньшее <tex> n <br/tex>Значит , нежели чем для <tex>p,\forall i = q \ldots n - p</tex>, поскольку <tex>\alpha [i + gcd(p-q, q] ) = \alpha[i + gcd(p], q) </tex><br/>Сделаем замену . А тогда по предположению индукции заключаем: <tex>j = i + qv </tex> и получим, что<br/>имеет период <tex>\forall j = 1 \ldots n - gcd(p - q, q)</tex>, . Учитывая <tex>\alpha [j] gcd(p-q, q) = \alpha[j + gcd(p - , q)]= r </tex>, можем сказать что <br/tex>Получили новый v <b/tex>имеет период длины</b> <tex>p - qr </tex>. Из предположения известно*: Как уже упоминалось, что НОД<tex>(p - q, q)\geqslant r </tex> {{---}} период строки, но НОДпоэтому <tex>|v| \geqslant (p - q, ) + q - r \geqslant q)</tex>, в следствие чего по '''лемме 2''' <tex>=w </tex>НОДимеет период <tex>(p, q)r </tex>.</li></ol>Следовательно утверждение доказано.
}}
 
== См. также ==
* [[Основные определения, связанные со строками]]
 
== Примечания ==
<references/>
 
== Источники информации ==
* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
* ''Lothaire M.'' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Навигация