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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Определения)
(Переделывание доказательства про НОД)
Строка 46: Строка 46:
 
Утверждение доказано.
 
Утверждение доказано.
 
}}
 
}}
 +
 +
{{Лемма
 +
|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 \leqslant n</tex>, то НОД<tex>(p, 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=
 
|proof=
−
Для удобства доказательства допишем перед строкой её копию и будем нумеровать символы новой строки не с <tex>1</tex> до <tex>2n</tex>, а с <tex>-n + 1</tex> до <tex>n</tex>. Назовём полученную строку <tex>\alpha</tex>.<br/>
+
 
−
Доказательство будем вести по индукции по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
 
−
(p + 1, 1), &  q = p.\end{cases}</tex><br/>
 
−
<ol>
 
−
<li>Для <tex> (1, 1) </tex> утверждение очевидно.</li>
 
−
<li>Пусть верно для всех пар меньших <tex>(p, q)</tex>.</li>
 
−
<li>Докажем, что верно для <tex>(p, q)</tex>.<br/>
 
−
Из определения периода:<br/>
 
−
<ul><tex>\forall i = -n + 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.</ul>
 
−
Значит <ul><tex>\forall i = 1 - q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex></ul>
 
−
Сделаем замену <tex>j = i + q</tex> и получим, что<br/>
 
−
<ul><tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex></ul>
 
−
Получили новый период длины <tex>p - q</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex><tex>=</tex>НОД<tex>(p, q)</tex>.</li>
 
−
</ol>
 
−
Следовательно утверждение доказано.
 
 
}}
 
}}
  

Версия 10:07, 8 мая 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].

  1. Для [math] x = 1 [/math] утверждение очевидно.
  2. Пусть верно для [math]x \leqslant m[/math].
  3. Докажем, что верно для [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] w [/math] имеет периоды [math] p [/math] и [math] q [/math], причём [math] p \lt q \leqslant |w| [/math]. Тогда суффикс и префикс [math] w [/math] длины [math] |w| - q [/math] имеют период [math] p - q [/math].
Доказательство:
[math]\triangleright[/math]

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

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

Поскольку [math] w [/math] имеет период [math] p [/math], выполнено [math] s_i = s_{i+p} [/math]

Также [math] w [/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] r | q [/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] a_i = a_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' [/math] и [math] j' [/math] такие, что [math] i \equiv i' \pmod q,\ j \equiv j' \pmod q [/math].
[math]\triangleleft[/math]


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

См. также

Основные определения, связанные со строками

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Период_и_бордер,_их_связь&oldid=36785»