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

Определения

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

Строка [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]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Для удобства доказательства допишем перед строкой её копию и будем нумеровать символы новой строки не с [math]1[/math] до [math]2n[/math], а с [math]-n + 1[/math] до [math]n[/math]. Назовём полученную строку [math]\alpha[/math]. Доказательство будем вести по индукции по парам [math](p, q)[/math], где [math] p \geqslant q [/math], а [math](p, q) + 1 = \begin{cases} (p, q + 1), & q \lt p;\\ (p + 1, 1), & q = p.\end{cases}[/math] Для [math] (1, 1) [/math] утверждение очевидно. Пусть верно для всех пар меньших [math](p, q)[/math]. Докажем, что верно для [math](p, q)[/math]. Из определения периода: [math]\forall i = -n + 1 \ldots n - p[/math], [math]\alpha [i] = \alpha[i + p] = \alpha[i + q][/math]. Значит [math]\forall i = 1 - q \ldots n - p[/math], [math]\alpha [i + q] = \alpha[i + p][/math] Сделаем замену [math]j = i + q[/math] и получим, что [math]\forall j = 1 \ldots n - (p - q)[/math], [math]\alpha [j] = \alpha[j + (p - q)][/math] Получили новый период длины [math]p - q[/math]. Из предположения известно, что НОД[math](p - q, q)[/math] — период строки, но НОД[math](p - q, q)[/math][math]=[/math]НОД[math](p, q)[/math]. Следовательно утверждение доказано.

[math]\triangleleft[/math]

См. также

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