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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Добавлена точка в конце предложения и убраны лишние "что")
м
Строка 16: Строка 16:
 
|statement= Если у строки длины <tex>n</tex> есть [[Период_и_бордер,_их_связь#Определения|бордер]] длины <tex>k</tex>, то у нее есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>n - k</tex>.
 
|statement= Если у строки длины <tex>n</tex> есть [[Период_и_бордер,_их_связь#Определения|бордер]] длины <tex>k</tex>, то у нее есть [[Период_и_бордер,_их_связь#Определения|период]] длины <tex>n - k</tex>.
 
|proof=
 
|proof=
Пусть дана строка <tex>\alpha</tex>.<br/>
+
Пусть дана строка <tex>\alpha</tex>.
Напишем формально определения бордера длины <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>k</tex> строки <tex>\alpha</tex>:
Сделаем замену <tex>x = n - k</tex>:<br/>
+
 
<ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>
+
: <tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.
 +
Сделаем замену <tex>x = n - k</tex>:
 +
: <tex>\forall i = 1 \ldots n - x</tex>, <tex>\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>.
 
}}
 
}}
Строка 38: Строка 40:
 
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем, что верно для <tex>x = m + 1</tex>.
 
*: Пусть верно для <tex>x \leqslant m</tex>. Докажем, что верно для <tex>x = m + 1</tex>.
 
*: Из определения периода имеем
 
*: Из определения периода имеем
*: <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,
+
*:: <tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,
 
*: а из предположения индукции
 
*: а из предположения индукции
*: <tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex>.
+
*:: <tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex>.
 
*: Значит получаем, что
 
*: Значит получаем, что
*: <tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,
+
*:: <tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,
 
*: следовательно
 
*: следовательно
*: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.
+
*:: <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.
 
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
 
*: Значит у строки есть период длины <tex>k(m + 1)</tex>.
  
Строка 73: Строка 75:
 
Заметим, что поскольку <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> |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>.  
+
Так как <tex> q </tex> <tex dpi=90>\,\vdots\, </tex> <tex> r </tex>, можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex> <ref>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойства сравнений]]</ref>.  
  
 
Помимо того <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> 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>.  
Строка 89: Строка 91:
 
|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> n = 1 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
+
*: При <tex> n = 2 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
 
* Переход
 
* Переход
*: Заметим что теперь <tex> q \ne p </tex> (так как <tex> n \ne 1 </tex>), поэтому без ограничения общности можем сказать, что <tex> q < p </tex>.
+
*: Заметим что теперь <tex> q \ne p </tex> (так как <tex> n > 2 </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>:  
Строка 100: Строка 102:
 
}}
 
}}
  
Ограничение <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></references>
  
 
== См. также ==
 
== См. также ==
[[Основные определения, связанные со строками]]
+
* [[Основные определения, связанные со строками]]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Версия 18:15, 12 мая 2014

Определения

Определение:
Строка [math]\alpha[/math] называется бордером строки [math]\beta[/math], если [math]\alpha[/math] одновременно является и суффиксом, и префиксом [math]\beta[/math].


Определение:
Число [math]p[/math] называется периодом строки [math]\alpha[/math], если [math]\forall i = 1 \ldots n - p[/math] [math]\alpha [i] = \alpha[i + p][/math].


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

Теорема:
Если у строки длины [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[/math], [math]\alpha [i] = \alpha[i + (n - k)][/math].

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

[math]\forall i = 1 \ldots n - x[/math], [math]\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[/math], [math]\alpha [i] = \alpha[i + k][/math],
    а из предположения индукции
    [math]\forall i = 1 \ldots n - km[/math], [math]\alpha [i] = \alpha[i + mk][/math].
    Значит получаем, что
    [math]\forall i = 1 \ldots n - km - k[/math], [math]\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k][/math],
    следовательно
    [math]\forall i = 1 \ldots n - k(m + 1)[/math], [math]\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] p \lt q \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] |v| \geqslant q [/math], то отрезок [math] [h, k] [/math] содержит ровно [math] q [/math] целых чисел, так что найдутся [math] i',\ j' \in [h, k] [/math] такие, что [math] i \equiv i' \pmod q,\ j \equiv j' \pmod q [/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] n = 2 [/math] видно, что [math] p = q = r [/math] и потому утверждение истинно.
  • Переход
    Заметим что теперь [math] q \ne p [/math] (так как [math] n \gt 2 [/math]), поэтому без ограничения общности можем сказать, что [math] q \lt p [/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) + q - r = (p - q) + q - \gcd(p - q, 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] p \gt q [/math] и по свойствам НОД), поэтому [math] |v| = |w| - q \geqslant (p + q - r) - q \geqslant q + (p - q) - r \geqslant q [/math], тогда по лемме 2 [math] w [/math] имеет период [math] r [/math].
[math]\triangleleft[/math]

Примечания

См. также