= Borders of a string
{synonym}

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.


 Border of a string (source code)