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]

For a string $s$, the value ${\pi }_i$ is the length of the longest proper prefix of $s_0\cdots s_i$ that is also its suffix. Repeatedly following these lengths lists all proper borders of a string; this is the failure-link information used by the Knuth-Morris-Pratt algorithm.

For a fixed word $w$, store the length of the longest suffix of the received stream that is also a prefix of $w$. On a new input symbol, append it to the represented prefix and select the longest resulting suffix that is a prefix of $w$. The complete-word state signals recognition. Its outgoing transitions retain proper suffix matches, allowing overlapping occurrences rather than automatically restarting from the empty prefix. This is the finite-state form of the prefix information used by the Knuth-Morris-Pratt algorithm.

For example, recognizing $1101$ needs suffix-prefix states of lengths zero through four. After a complete match followed by one, the last two symbols are $11$, so the next state retains length two. This permits the second match in $1101101$ without clearing the useful suffix.

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.

A string-searching algorithm locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text ababa and pattern aba, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct algorithm compares the pattern at each start and can require $O(nm)$ character comparisons. The Knuth-Morris-Pratt algorithm reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, Unicode code points and user-perceived characters can describe different tasks.