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.

A proper border of a string is a string prefix that is also a string suffix and is shorter than the complete string. With zero-based lengths, its length $b$ satisfies $0\le b<m$ for a length-$m$ string, if the empty string is allowed. Specify that convention when counting borders.

For ababa, the nonempty proper borders are a and aba; the complete ababa is a border of a string but not a proper one. A proper border of length $b$ allows two copies of the string to overlap with displacement $m-b$. The border aba therefore explains the shift of two between overlapping occurrences of ababa in abababa.

The prefix function stores the longest proper-border length of each prefix. For ababa, following these lengths gives $3\to 1\to 0$, listing successively shorter candidate overlaps. The Knuth-Morris-Pratt algorithm uses this chain after a mismatch, retaining a suffix already known to match rather than comparing the whole pattern again.