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

Определения

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

Строка [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] 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] также является периодом этой строки.

См. также

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