Период и бордер, их связь

Определения

Определение:

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

Определение:

Число [math]p[/math] называется периодом строки [math]\alpha[/math], если [math] \quad \forall i = 1 \ldots n - p: \quad \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: \ \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] . Помимо того [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