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

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

Теорема:

Если у строки длины [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]