Prefix Function, Borders & KMP

Borders and Failure Information

A border of a non-empty string $S$ is a proper prefix that is also a suffix. For $S=\text{"abababa"}$, the strings $\text{"a"}$, $\text{"aba"}$, and $\text{"ababa"}$ are borders. The empty string is often treated as a trivial border, while $S$ itself is excluded by “proper.”

Borders are nested. If $B$ is the longest proper border of $S$, every shorter border of $S$ is also a border of $B$. Thus all border lengths can be recovered by repeatedly asking for the longest border of the preceding border.

The prefix function $\pi[i]$ is the length of the longest proper border of $S[0\dots i]$. When a comparison fails after $j$ symbols, the next viable candidate has length $\pi[j-1]$. This failure information is reused by both preprocessing and KMP search.

Building the Prefix Function

Assume $\pi[0],\dots,\pi[i-1]$ are known and set $j=\pi[i-1]$. The invariant is $S[0\dots j)=S[i-j\dots i)$, so only $S[j]$ and $S[i]$ remain to compare. If they match, set $\pi[i]=j+1$. Otherwise, any shorter candidate must be a border of the current candidate, so replace $j$ with $\pi[j-1]$ and continue down the border chain.

Preprocessing is linear. Successful extensions increase $j$ by at most one per outer iteration, while every fallback strictly decreases it. Across the complete scan, total decrease cannot exceed accumulated increase.

def prefix_function(text: str) -> list[int]:
    """Return longest proper-border lengths for every prefix."""
    pi = [0] * len(text)
    for i in range(1, len(text)):
        border = pi[i - 1]
        while border > 0 and text[i] != text[border]:
            border = pi[border - 1]
        if text[i] == text[border]:
            border += 1
        pi[i] = border
    return pi


def border_lengths(text: str) -> list[int]:
    """Return non-empty proper border lengths in increasing order."""
    if not text:
        return []
    pi = prefix_function(text)
    result: list[int] = []
    border = pi[-1]
    while border > 0:
        result.append(border)
        border = pi[border - 1]
    result.reverse()
    return result


if __name__ == "__main__":
    assert prefix_function("") == []
    assert prefix_function("a") == [0]
    assert prefix_function("aaaaa") == [0, 1, 2, 3, 4]
    assert prefix_function("abababa") == [0, 0, 1, 2, 3, 4, 5]
    assert prefix_function("abacaba") == [0, 0, 1, 0, 1, 2, 3]
    assert border_lengths("abababa") == [1, 3, 5]
    assert border_lengths("abacaba") == [1, 3]
    assert border_lengths("abcdef") == []
    for sample in ["aaaaa", "abababa", "abacaba", "abcdef"]:
        print(sample, prefix_function(sample), border_lengths(sample))

KMP Search and Proof

KMP scans the text while maintaining $j$, the length of the pattern prefix matching the suffix of text processed so far. If $T[i]=P[j]$, increment $j$. On mismatch, replace $j$ with $\pi[j-1]$ until the symbols match or $j=0$. Each fallback preserves the longest already matched suffix that could still begin an occurrence, so the text index never moves backward.

When $j=m$, report start $i-m+1$ and assign $j=\pi[m-1]$ rather than zero to preserve overlapping matches. Preprocessing is $O(m)$ and searching is $O(n)$: each successful transition increases $j$, every fallback decreases it, and total decrease is bounded by total prior increase.

Worked Example

KMP Trace

Search for $P=\text{"aaaab"}$ in $T=\text{"aaaaaaaaab"}$. The prefix array is $[0,1,2,3,0]$.

Indices $0$ through $3$ match four a symbols, so $j=4$.
At index $4$, a mismatches expected b. Fall back to $\pi[3]=3$; the same text a now matches $P[3]$, restoring $j=4$.
Indices $5$ through $8$ repeat one mismatch, one fallback, and one match. The text index never retreats.
At index $9$, b matches $P[4]$, giving $j=5$. Report start $9-5+1=5$.
A fallback occurs at nearly every position, but each is paid for by an earlier increase of $j$, demonstrating the amortized linear bound.

Beyond Matching

For a length-$n$ string, $p=n-\pi[n-1]$ is its shortest-period candidate. The string is an exact repetition of a shorter block precisely when $n\bmod p=0$; then its exponent is $n/p$. Otherwise, $p$ may still be a period without tiling the complete string.

Enumerate borders by starting at $k=\pi[n-1]$ and repeatedly assigning $k=\pi[k-1]$. Prefix occurrences are counted by recording how often every $\pi[i]$ value appears, propagating counts from longer prefixes to failure-link parents in decreasing length order, and adding each prefix's occurrence at position zero.

To search with one prefix-function computation, build pattern + sentinel + text using a sentinel outside both alphabets. Values equal to the pattern length identify occurrence endings.

For a length-$n$ string: longest border $=\pi[n-1]$; the next border of length $k$ has length $\pi[k-1]$; shortest-period candidate $=n-\pi[n-1]$; and an exact power exists when that candidate divides $n$. Failure-link propagation turns the same border tree into occurrence counts for every prefix.