= Proper border of a string
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\leq 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 of a string>[proper-border] length of each <string prefix>[prefix]. For `ababa`, following these lengths gives $3\to1\to0$, listing successively shorter candidate overlaps. The <Knuth-Morris-Pratt algorithm> uses this chain after a mismatch, retaining a <string suffix>[suffix] already known to match rather than comparing the whole pattern again.
Back to article page
