 Border of a string

A border of a string is a string that is both a prefix and a suffix. A proper border is shorter than the whole string; the empty string is often included. The string ababa has proper nonempty borders a and aba. A border of length $b$ in a length-$m$ string corresponds to an overlap displacement $m-b$. The Knuth-Morris-Pratt algorithm uses a chain of such borders to decide how much of a partial match survives a mismatch, avoiding comparison of characters already known to agree.