Найдовший бордюр

Бордюр (межа, край) рядка $S$ — це будь-який правильний префікс рядка, який дорівнює його суфіксу.

Наприклад, рядок S = abaababaabaab має два непорожніх бордюри: $ab$ та $abaab$.

Рядок S = abaabaab також має два таких бордюри — $ab$ і $abaab$, причому другий бордюр перекривається.

Рядок довжини $n$, що складається з одного повторюваного символу (наприклад, $aaaaaaaa$ або a^{8}), має n-1 бордюр. Для S = a^{8} ці бордюри такі: $a$, $aa$, $aaa$, $aaaa$, $aaaaa$, $aaaaaa$, $aaaaaaa$.

Термін "правильний префікс" виключає бордюр, що збігається з усім рядком.

Довжина бордюру — це кількість символів у ньому.

Природним узагальненням бордюру є найдовший бордюр — найдовший правильний префікс рядка, який збігається з його суфіксом.