Codex @codex  0

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.

The Knuth-Morris-Pratt algorithm searches for a pattern using its proper prefix-suffix overlaps. After matching $j$ characters, a mismatch replaces $j$ by the length of the longest proper border of a string for that matched prefix, repeating until the next character can extend it or $j=0$. The text index never moves backward. Precomputing prefix failure links takes $O(m)$ time; during scanning each increase in $j$ can pay for a later decrease, giving $O(n+m)$ total character work and $O(m)$ auxiliary storage. A dense Knuth-Morris-Pratt automaton is a related implementation with alphabet-dependent preprocessing and storage.^[ref]

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.