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

Связь периода и бордера

Теорема:

Если у строки длины [math]n[/math] есть бордер длины [math]k[/math], то у нее есть период длины [math](n - k)[/math].

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

[math]\triangleright[/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]|k \cdot x|[/math], где [math] x \in N[/math].

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

[math]\triangleright[/math]

Пусть длина строки равна [math]n[/math]. Доказательство будем вести по индукции по числу [math]x[/math]. Для [math] x = 1 [/math] утверждение очевидно. Пусть верно для [math]x = 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 - k[/math], [math]\alpha [i] = \alpha[i + m \cdot k][/math] Значит получаем, что для [math]\forall i = 1 \ldots n - k[/math] [math]\alpha [i] = \alpha [i + m \cdot k] = \alpha[i + m \cdot k + k][/math], следовательно [math]\forall i = 1 \ldots n + 1 - k[/math], [math]\alpha [i] = \alpha[i + (m + 1) \cdot k][/math]. Значит у строки есть период длины [math] |(m + 1) \cdot k|[/math]. Утверждение доказано.

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

Пусть [math] p \gt q [/math], тогда для [math]\forall i = 1 \ldots n - q[/math], [math]\alpha [i] = \alpha[i + p] = \alpha[i + q][/math]. Значит для [math]\forall i = 1 \ldots n - (p - q)[/math], [math]\alpha [i] = \alpha[i + (p - q)][/math] Теперь, следуя алгоритму Евклида, если [math] q \gt = p - q [/math], получим [math]\alpha [i] = \alpha[i + (q - (p - q))][/math], иначе [math]\alpha [i] = \alpha[i + (p - q) - q][/math]. Будем выполнять такие действия, пока не получим НОД[math](p, q)[/math]. Это будет выполнятся для [math]\forall i [/math]. Следовательно будет период длины НОД[math](p, q)[/math].

[math]\triangleleft[/math]