Border of a string

A string $u$ is said to be a border of a string $w$ if it is both a prefix and a suffix of $w$, and is strictly shorter than $w$.

Examples

• aba is a border of abacaba
• aa is a border of aabbbbaa
• ε is a border of abc, where ε denotes the empty string.

Properties

• A string $w$ can have at most $\mid w\mid$ borders, including the empty string.