Редактирование: Период и бордер, их связь

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
==Определения==
 +
{{Определение
 +
|definition =
 +
Строка <tex>\alpha</tex> называется '''бордером''' строки <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и [[Основные определения, связанные со строками#Отношения между строками|суффиксом]], и [[Основные определения, связанные со строками#Отношения между строками|префиксом]] <tex>\beta</tex>.
 +
|id=border
 +
}}
 +
 +
{{Определение
 +
|definition =
 +
Число <tex>p</tex> называется '''периодом''' строки <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
 +
|id=border
 +
}}
 +
 
==Связь периода и бордера==
 
==Связь периода и бордера==
 
{{Теорема
 
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#border | бордер]] длины <tex>k</tex>, то у нее также имеется [[Основные определения, связанные со строками#period | период]] длины <tex>n - k</tex>.
+
|statement= Если у строки длины <tex>n</tex> есть [[Период_и_бордер,_их_связь#Определения|бордер]] длины <tex>k</tex>, то у нее есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>n - k</tex>.
 
|proof=
 
|proof=
Пусть дана строка <tex>\alpha</tex>.
+
Пусть дана строка <tex>\alpha</tex>.<br/>
 
+
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/>
Напишем формально определение бордера длины <tex>k</tex> строки <tex>\alpha</tex>:
+
<ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul>
 
+
Сделаем замену <tex>x = n - k</tex>:<br/>
: <tex>\forall i = 1 \ldots k: \ \alpha [i] = \alpha[i + (n - k)]</tex>
+
<ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>  
Сделаем замену <tex>x = n - k</tex>:
 
: <tex>\forall i = 1 \ldots n - x: \ \alpha [i] = \alpha[i + x]</tex>
 
 
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
 
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
 
}}
 
}}
Строка 15: Строка 26:
 
==Свойства периода==
 
==Свойства периода==
 
{{Теорема
 
{{Теорема
|author=о кратном периоде
+
|statement= Если у строки есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>k</tex>, то у нее есть период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|statement= Если у строки есть период длины <tex>k</tex>, то у нее имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
 
 
|proof=
 
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.
+
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.<br/>
 
+
Доказательство будем вести по индукции по числу <tex>x</tex>.<br/>
Доказательство будем вести индукцией по числу <tex>x</tex>.
+
<ol>
 
+
<li>Для <tex> x = 1 </tex> утверждение очевидно.</li>
* База
+
<li>Пусть верно для <tex>x \leqslant m</tex>.</li>
*: Для <tex> x = 1 </tex> утверждение очевидно.
+
<li>Докажем, что верно для <tex>x = m + 1</tex>.<br/>
* Переход
+
Из определения периода имеем, что<br/>
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем то же для <tex>x = m + 1</tex>.
+
<ul><tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,</ul>
*: Из определения периода имеем
+
а из предположения индукции, что<br/>
*:: <tex>\forall i = 1 \ldots n - k: \ \alpha [i] = \alpha[i + k]</tex>
+
<ul><tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex></ul>
*: а из предположения индукции
+
Значит получаем, что<br/>
*:: <tex>\forall i = 1 \ldots n - km: \ \alpha [i] = \alpha[i + mk]</tex>
+
<ul><tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,</ul>
*: С учётом этого получаем, что
+
следовательно<br/>
*:: <tex>\forall i = 1 \ldots n - km - k: \ \alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>
+
<ul>для <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.</ul>
*: следовательно
+
Значит у строки есть период длины <tex>k(m + 1)</tex>.<br/></li>
*:: <tex>\forall i = 1 \ldots n - k(m + 1): \ \alpha [i] = \alpha[i + k(m + 1)]</tex>
+
</ol>
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
 
 
 
 
Утверждение доказано.
 
Утверждение доказано.
 
}}
 
}}
  
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
+
 
 +
Перед доказательством следующей теоремы сначала докажем пару интуитивно понятных лемм.
  
 
{{Лемма
 
{{Лемма
 
|about=1
 
|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>.  
+
|statement= Пусть строка <tex> s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> p < q \leqslant |s| </tex>. Тогда суффикс и префикс <tex> s </tex> длины <tex> |s| - q </tex> имеют период <tex> p - q </tex>.  
 
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
 
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
  
Требуется показать: <tex> s_i = s_{i+p-q} \ \ (i = 1 \dots n-p\ , \ n=|s|) </tex>  
+
Требуется показать что <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> 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>   
 
Также <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>   
 
}}
 
}}
Строка 54: Строка 63:
 
{{Лемма
 
{{Лемма
 
|about=2
 
|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>.
+
|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>.  
 
|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> 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> |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> q|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>.
+
Помимо того <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>.  
 
 
В виду того, что <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>.  
 
  
 
}}
 
}}
Строка 73: Строка 80:
  
 
{{Теорема
 
{{Теорема
|statement= Если у строки <tex>w</tex> есть периоды <tex>p</tex> и <tex>q</tex>, где <tex> |w| \geqslant p + q - \gcd(p, q) </tex>, то <tex>\gcd(p, q)</tex> также является периодом этой строки.
+
|statement= Если у строки <tex>w</tex> есть периоды <tex>p</tex> и <tex>q</tex>, где <tex> |w| \geqslant p + q - GCD(p, q) </tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
 
|author=Фин и Вильф
 
|author=Фин и Вильф
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
+
|proof=Обозначим <tex> r = GCD(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
 
 
В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> \max(p, q) > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
 
 
* База
 
* База
*: Истинность утверждения следует из <tex> p = q = r </tex>.
+
*: При <tex> n = 1 </tex> видно, что <tex> p = q = r </tex> и утверждение истинно.
 
* Переход
 
* Переход
*: В силу того, что <tex> p \ne q </tex>, без ограничения общности будем считать <tex> q < p </tex> (вообще говоря, исходя из свойств НОД можно дать более строгую оценку: <tex> p - q \geqslant r </tex>, чем мы позже воспользуемся).
+
*: Заметим что теперь <tex> q \ne p </tex>, поэтому без ограничения общности можем сказать что, <tex> q < p </tex>.
 
*: Пусть <tex> w = uv </tex>, где <tex> |u| = q </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>:  
+
*: По лемме 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| = |w| - q \geqslant (p - q) + q - r = (p - q) + q - GCD(p - q, q) </tex>.
*: Ещё заметим, что для периодов <tex> p - q,\ q </tex> будет меньшее <tex> n </tex>, нежели чем для <tex> p,\ q </tex>, поскольку <tex> \gcd(p-q, q) = \gcd(p, 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> 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> |v| \geqslant (p - q) + q - r \geqslant q </tex>, в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
+
*: Ещё заметим, что <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| = |w| - q \geqslant (p - q) + q - r \geqslant q </tex>, тогда по лемме 2 <tex> w </tex> имеет период <tex> r </tex>.
 +
 
 
}}
 
}}
 +
 +
Ограничение <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>, и периода <tex> 1 </tex> у неё нет.
  
 
== См. также ==
 
== См. также ==
* [[Основные определения, связанные со строками]]
+
[[Основные определения, связанные со строками]]
 
 
== Примечания ==
 
<references/>
 
 
 
== Источники информации ==
 
* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
 
* ''Lothaire M.'' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: