Материал из Викиконспекты
Определения
| Определение: |
| Строка [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] 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] r [/math] , можем написать [math] i \equiv i' \pmod r,\ j \equiv j' \pmod r [/math].
Помимо того [math] i \equiv j \pmod r [/math], тогда верно и [math] i' \equiv j' \pmod r [/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 = 1 [/math] видно, что [math] p = q = r [/math] и потому утверждение истинно.
- Переход
- Заметим что теперь [math] q \ne p [/math] (так как [math] n \ne 1 [/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] |
Ограничение [math] |w| \geqslant p + q - \gcd(p, q) [/math] существенно. Например строка [math] w = abaababaaba [/math] имеет периоды [math] 5 [/math] и [math] 8 [/math], её длина [math] 11 \lt 5 + 8 - 1 [/math], и периода [math] 1 [/math] у неё нет.
См. также
