Период и бордер, их связь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства периода)
(не показаны 42 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
==Связь периода и бордера==
 
==Связь периода и бордера==
 
{{Теорема
 
{{Теорема
|statement= Если у строки длины <tex>|n|</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>|k|</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>|n - k|</tex>.
+
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#border | бордер]] длины <tex>k</tex>, то у нее также имеется [[Основные определения, связанные со строками#period | период]] длины <tex>n - k</tex>.
 
|proof=
 
|proof=
 
Пусть дана строка <tex>\alpha</tex>.
 
Пусть дана строка <tex>\alpha</tex>.
Напишем формально определения бордера длины <tex>|k|</tex> строки <tex>\alpha</tex>:<br/>
+
 
<tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/>
+
Напишем формально определение бордера длины <tex>k</tex> строки <tex>\alpha</tex>:
Сделаем замену <tex>x = n - k</tex>:<br/>
+
 
<tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.
+
: <tex>\forall i = 1 \ldots k: \ \alpha [i] = \alpha[i + (n - k)]</tex>
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>|n - k|</tex>.
+
Сделаем замену <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>.
 
}}
 
}}
  
 
==Свойства периода==
 
==Свойства периода==
 
{{Теорема
 
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|kx|</tex>, где <tex> x \in N</tex>.
+
|author=о кратном периоде
 +
|statement= Если у строки есть период длины <tex>k</tex>, то у нее имеется также период длины <tex>kx</tex>, где <tex> x \in N</tex>.
 
|proof=
 
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex> \alpha </tex>.<br/>
+
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.
Доказательство будем вести по индукции по числу <tex>x</tex>.<br/>
+
 
Для <tex> x = 1 </tex> утверждение очевидно.<br/>
+
Доказательство будем вести индукцией по числу <tex>x</tex>.
Пусть верно для <tex>x = m</tex>. Докажем, что верно для <tex>x = m + 1</tex>.<br/>
+
 
Из определения периода имеем, что<br/>
+
* База
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>, а из предположения индукции, что<br/>
+
*: Для <tex> x = 1 </tex> утверждение очевидно.
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/>
+
* Переход
Значит получаем, что<br/>
+
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем то же для <tex>x = m + 1</tex>.
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>, следовательно<br/>
+
*: Из определения периода имеем
для <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + (m + 1)k]</tex>.<br/>
+
*:: <tex>\forall i = 1 \ldots n - k: \ \alpha [i] = \alpha[i + k]</tex>
Значит у строки есть период длины <tex> |(m + 1)k|</tex>.<br/>
+
*: а из предположения индукции
 +
*:: <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>
 +
*: следовательно
 +
*:: <tex>\forall i = 1 \ldots n - k(m + 1): \ \alpha [i] = \alpha[i + k(m + 1)]</tex>
 +
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
 +
 
 
Утверждение доказано.
 
Утверждение доказано.
 
}}
 
}}
 +
 +
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
 +
 +
{{Лемма
 +
|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>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</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> также является периодом этой строки.
|proof=
+
|author=Фин и Вильф
Пусть строка равна <tex> \alpha </tex>, а <tex> p > q </tex>, тогда<br/>  
+
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>
+
 
Значит для <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/>
+
В случае <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>j = i + q</tex> и получим, что
+
* База
для <tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex><br/>
+
*: Истинность утверждения следует из <tex> p = q = r </tex>.
Получили новый период длины <tex>|p - q|</tex>. Пусть теперь <tex>p = max(p - q, q)</tex>, а <tex>q = min(p - q, q)</tex>.<br/>
+
* Переход
Будем повторять алгоритм сначала, пока <tex>p <> q</tex>.
+
*: В силу того, что <tex> p \ne q </tex>, без ограничения общности будем считать <tex> q < p </tex> (вообще говоря, исходя из свойств НОД можно дать более строгую оценку: <tex> p - q \geqslant r </tex>, чем мы позже воспользуемся).
Видно, что представленный алгоритм - это алгоритм Евклида. Значит при его завершении получим, что последний найденный период равен НОД<tex>(p, 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>:
 +
*: <tex> |v| = |w| - q \geqslant (p + q - r) - 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> p - q \geqslant r </tex>, поэтому <tex> |v| \geqslant (p - q) + q - r \geqslant q </tex>, в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Основные определения, связанные со строками]]
 +
 +
== Примечания ==
 +
<references/>
 +
 +
== Источники информации ==
 +
* [[wikipedia:en:Substring | Wikipedia {{---}} Substring ]]
 +
* ''Lothaire M.'' Algebraic Combinatorics on Words {{---}} Cambridge University Press, 2002. {{---}} с. 272. {{---}} ISBN 0-521-81220-8
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 21:39, 15 февраля 2015

Связь периода и бордера

Теорема:
Если у строки длины [math]n[/math] есть бордер длины [math]k[/math], то у нее также имеется период длины [math]n - k[/math].
Доказательство:
[math]\triangleright[/math]

Пусть дана строка [math]\alpha[/math].

Напишем формально определение бордера длины [math]k[/math] строки [math]\alpha[/math]:

[math]\forall i = 1 \ldots k: \ \alpha [i] = \alpha[i + (n - k)][/math]

Сделаем замену [math]x = n - k[/math]:

[math]\forall i = 1 \ldots n - x: \ \alpha [i] = \alpha[i + x][/math]
Получили определение периода длины [math]x[/math]. Но [math]x = n - k[/math], значит у строки [math]\alpha[/math] есть период длины [math]n - k[/math].
[math]\triangleleft[/math]

Свойства периода

Теорема (о кратном периоде):
Если у строки есть период длины [math]k[/math], то у нее имеется также период длины [math]kx[/math], где [math] x \in N[/math].
Доказательство:
[math]\triangleright[/math]

Пусть длина строки равна [math]n[/math], сама строка — [math]\alpha[/math].

Доказательство будем вести индукцией по числу [math]x[/math].

  • База
    Для [math] x = 1 [/math] утверждение очевидно.
  • Переход
    Пусть верно для [math]x \leqslant m[/math]. Докажем то же для [math]x = m + 1[/math].
    Из определения периода имеем
    [math]\forall i = 1 \ldots n - k: \ \alpha [i] = \alpha[i + k][/math]
    а из предположения индукции
    [math]\forall i = 1 \ldots n - km: \ \alpha [i] = \alpha[i + mk][/math]
    С учётом этого получаем, что
    [math]\forall i = 1 \ldots n - km - k: \ \alpha [i] = \alpha [i + mk] = \alpha[i + mk + k][/math]
    следовательно
    [math]\forall i = 1 \ldots n - k(m + 1): \ \alpha [i] = \alpha[i + k(m + 1)][/math]
    Значит у строки есть период длины [math]k(m + 1)[/math].
Утверждение доказано.
[math]\triangleleft[/math]

Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.

Лемма (1):
Пусть строка [math] s [/math] имеет периоды [math] p [/math] и [math] q [/math], причём [math] q \lt p \leqslant |s| [/math]. Тогда суффикс и префикс [math] s [/math] длины [math] |s| - q [/math] имеют период [math] p - q [/math].
Доказательство:
[math]\triangleright[/math]

Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.

Требуется показать: [math] s_i = s_{i+p-q} \ \ (i = 1 \dots n-p\ , \ n=|s|) [/math]

Исходя из того, что [math] s [/math] имеет период [math] p [/math], выполнено [math] s_i = s_{i+p} [/math]

Также [math] s [/math] имеет период [math] q [/math] и из ограничений на [math] i [/math] верно [math] 1 \leqslant i + p - q \leqslant n - q [/math], поэтому [math] s_{i+p-q} = s_{i+p} [/math]
[math]\triangleleft[/math]
Лемма (2):
Пусть строка [math] w [/math] имеет период [math] q [/math], и существует [math] v [/math] подстрока [math] w [/math] такая, что [math] |v| \geqslant q [/math] и [math] v [/math] имеет период [math] r [/math], где [math] q [/math] [math]\,\vdots\, [/math] [math] r [/math]. Тогда [math] w [/math] имеет период [math] r [/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math] w = s_1 \dots s_n,\ v = s_h \dots s_k [/math], где [math] 1 \leqslant h \lt k \leqslant n [/math].

Требуется показать: [math] s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) [/math].

Зафиксируем [math] i [/math] и [math] j [/math]. Заметим, что поскольку [math] |v| \geqslant q [/math], отрезок [math] [h, k] [/math] содержит по меньшей мере [math] q [/math] целых чисел, так что найдутся [math] i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q,\ i \ne j [/math].

С учётом [math] q [/math] [math]\,\vdots\, [/math] [math] r [/math] можем написать [math] i \equiv i' \pmod r,\ j \equiv j' \pmod r [/math] [1].

Помимо того [math] i \equiv j \pmod r [/math], а в таком случае верно и [math] i' \equiv j' \pmod r [/math].

Теперь воспользуемся следующим фактом: если строка [math] s [/math] имеет период [math] r [/math], то [math] i \equiv j \pmod r \ \Rightarrow\ s_i = s_j [/math] (действительно, без ограничения общности можем сказать, что [math] i \leqslant j [/math], и исходя из этого выстроить цепочку равенств [math] s_i = s_{i + r},\ \ s_{i + r} = s_{i + 2r},\ \ \dots \ , \ s_{j - r} = s_j [/math]).

В виду того, что [math] w [/math] имеет период [math] q [/math], имеют место равенства [math] s_i = s_{i'}\ [/math] и [math]\ s_j = s_{j'} [/math]. Кроме того [math] v [/math] имеет период [math] r [/math], потому верно [math] s_{i'} = s_{j'} [/math]. Тогда и [math] s_i = s_j [/math].
[math]\triangleleft[/math]


Теорема (Фин и Вильф):
Если у строки [math]w[/math] есть периоды [math]p[/math] и [math]q[/math], где [math] |w| \geqslant p + q - \gcd(p, q) [/math], то [math]\gcd(p, q)[/math] также является периодом этой строки.
Доказательство:
[math]\triangleright[/math]

Обозначим [math] r = \gcd(p, q) [/math]. Доказательство будем вести индукцией по [math] n = (p + q) / r [/math].

В случае [math] p = q [/math] видим что [math] n = 2 [/math], что соответствует базе, в то время как при [math] p \ne q [/math] выполнено [math] \max(p, q) \gt \gcd(p, q) [/math], так что [math] n \gt 2 [/math].

  • База
    Истинность утверждения следует из [math] p = q = r [/math].
  • Переход
    В силу того, что [math] p \ne q [/math], без ограничения общности будем считать [math] q \lt p [/math] (вообще говоря, исходя из свойств НОД можно дать более строгую оценку: [math] p - q \geqslant r [/math], чем мы позже воспользуемся).
    Пусть [math] w = uv [/math], где [math] |u| = q [/math].
    По лемме 1 [math] v [/math] имеет период [math] p - q [/math], также [math] v [/math] имеет период [math] q [/math] как подстрока [math] w [/math]. Теперь рассмотрим длину [math] v [/math]:
    [math] |v| = |w| - q \geqslant (p + q - r) - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) [/math].
    Ещё заметим, что для периодов [math] p - q,\ q [/math] будет меньшее [math] n [/math], нежели чем для [math] p,\ q [/math], поскольку [math] \gcd(p-q, q) = \gcd(p, q) [/math]. А тогда по предположению индукции заключаем: [math] v [/math] имеет период [math] \gcd(p-q, q)[/math]. Учитывая [math] \gcd(p-q, q) = \gcd(p, q) = r [/math], можем сказать что [math] v [/math] имеет период [math] r [/math].
    Как уже упоминалось, [math] p - q \geqslant r [/math], поэтому [math] |v| \geqslant (p - q) + q - r \geqslant q [/math], в следствие чего по лемме 2 [math] w [/math] имеет период [math] r [/math].
[math]\triangleleft[/math]

См. также

Примечания

Источники информации

  • Wikipedia — Substring
  • Lothaire M. Algebraic Combinatorics on Words — Cambridge University Press, 2002. — с. 272. — ISBN 0-521-81220-8