The Prefix Function and Linear-Time Exact Matching

A pattern matcher reads a text once and reports every position where a pattern occurs. The naive version tries every alignment and compares characters left to right, abandoning an alignment at the first mismatch. On most inputs it is fast. On inputs built to defeat it — a text of aaaa…a and a pattern of aaa…ab — it compares nearly m characters at each of the n−m+1 alignments and performs Θ(nm) character comparisons, with no useful result until the final position.

The failure is not in the number of alignments, which is inherent, but in what is remembered. After comparing aaaa against aaaa and failing on b, the matcher has established that the text at that position contains a run of a’s. The next alignment starts one position to the right and re-establishes the same fact from scratch. A table of borders lets the matcher keep that knowledge.

Discarding work at every mismatch

Consider the pattern ababaca. Suppose the first five characters match and the sixth does not. The naive matcher shifts by one and compares from the start again, testing babaca against the text. But the five matched characters were ababa, and the pattern itself says that the longest proper prefix of ababa that is also a suffix is aba. Any alignment that skips those three characters cannot match: the text’s aba already agrees with the pattern’s prefix, so the matcher may resume with three characters still considered matched and compare the text against pattern position 3.

That is the entire idea. The prefix function stores, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix of it. With that table a mismatch at pattern position k resumes at position π[k−1] instead of position 0, and no text character is ever re-read.

The prefix function as a compressed transition table

For a pattern P of length m, define π[i] for 0 ≤ i < m as the largest k < i+1 such that P[0..k−1] = P[i−k+1..i]. By definition π[0] = 0, because no proper prefix of a one-character string exists. For ababaca the table is [0, 0, 1, 2, 3, 0, 1]: the prefix ababa has border aba of length 3, and the full pattern has border a.

A deterministic automaton for the same pattern would have m+1 states and a transition for every character of the alphabet, giving O(m·|Σ|) space. The prefix function is that automaton with the transitions left implicit: the “go to the longest border” edge is stored once per state, and the other edges are recovered by walking the chain of borders until a character matches. This is the design constraint that makes the algorithm practical for large alphabets. For a byte alphabet the table is 256·m entries, tolerable for a short pattern; for Unicode code points it is unusable, and for a pattern of a few thousand characters even the byte table wastes cache lines on transitions that will never be taken.

Searching with the table needs one integer of state:

def prefix_function(p):
    pi = [0] * len(p)
    for i in range(1, len(p)):
        k = pi[i - 1]
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to the border of the border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def find_all(text, pattern):
    if not pattern:
        return []
    pi = prefix_function(pattern)
    hits, k = [], 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - len(pattern) + 1)
            k = pi[k - 1]          # allow overlapping occurrences
    return hits

The final assignment inside the loop is the detail most often omitted. Resetting k to 0 after a match would miss overlapping occurrences such as aa in aaa; resuming at π[m−1] reports all of them, and the sum of reported positions is still linear because each report is charged to a text character that caused an increment.

Why the failure chain cannot be walked too often

A single mismatch can trigger many fallback steps. Matching aaaa…ab against aaaa…a walks the chain from length m−1 down to 0 at one text position, which costs Θ(m) work there. The linear bound is therefore not per character; it is a statement about the whole scan.

The argument counts state changes. The variable k increases by at most one per text character, so over n characters it increases at most n times. Every step of the fallback loop strictly decreases k, and k never becomes negative, so the total number of fallback steps across the entire scan is at most the total number of increases, which is at most n. Each character comparison in the inner loop either triggers a fallback or terminates the loop, so the total number of comparisons is bounded by 2n. The same accounting applies to the table construction, where the “text” is the pattern itself, so building π costs at most 2m comparisons.

Two consequences follow. The bound is amortized, so a real-time system that must bound the latency of each individual step cannot rely on it; a single position can cost O(m). And the bound is tight in the worst case, but only for highly periodic inputs. On ordinary text the fallback loop rarely runs more than once, and the constant factor is dominated by the unpredictable branch rather than by arithmetic.

Building the table from the table

The construction loop is the search loop applied to the pattern against itself, with the first character skipped. At index i the value π[i−1] already describes the longest border of the previous prefix; if the next character extends that border, π[i] = π[i−1] + 1. Otherwise the candidate shortens to the border of the border, and so on, until either a character matches or the candidate reaches 0. This is why the table can be built in one left-to-right pass with no recursion and why the same code appears in both phases with the roles of text and pattern exchanged.

The border chain is itself useful beyond matching. Every border of the whole pattern appears in the chain π[m−1], π[π[m−1]−1], and so on down to zero, so the chain enumerates all proper borders in decreasing length. The smallest positive period of the pattern is m − π[m−1], and if that period divides m the pattern is a repetition of a shorter block — the fact behind the standard test for whether a string is a power of some primitive word. The chain can hold Θ(m) entries, as in aaaa…a, so enumerating borders is linear in the pattern length but not constant.

What the table cannot tell you

The prefix function answers one question: where to resume after a mismatch when the pattern is matched left to right. It gives no help when comparisons are cheaper in another order. Boyer–Moore scans the pattern right to left and uses the character that caused the mismatch to skip whole alignments; on natural-language text that usually beats KMP by a wide margin, because most alignments fail on the last character and the skip is long. The prefix function is the better choice when the text is streamed and cannot be revisited, or when the pattern is short and the alphabet is large.

It also does not extend to a set of patterns. Running KMP once per pattern costs Θ(k(n+m)) for k patterns; the failure links of all patterns can instead be merged into a single automaton, which is what Aho–Corasick failure links construct. Nor does it tolerate errors: a mismatch is a mismatch, and approximate matching needs a different state, discussed under bit-parallel approximate matching.

The hashing alternative occupies a different point in the space. A polynomial rolling hash compares fixed-width fingerprints instead of characters, which makes each alignment O(1) in expectation but introduces a collision probability that must be argued about rather than proved away.

One practical edge case deserves mention because it is invisible in the pseudocode: what counts as a character. If the pattern and text are UTF-8 byte strings, a match can begin in the middle of a multi-byte sequence and still satisfy the byte comparison. Operating on code points avoids that but requires decoding first, which costs a pass over the input and memory proportional to the decoded length. Matching on bytes is correct only when the caller wants byte-level semantics, as in a binary protocol parser, and even then the reported offsets are byte offsets.

Finally, the space cost is m integers for the table. For a pattern of a few characters, that is more memory than the pattern itself, and the naive loop is competitive because it has no preprocessing to pay for and its whole state is two indices into strings that are already in cache. Implementations in standard libraries therefore dispatch on pattern length, using a plain scan below a small threshold and the table above it. The threshold is an implementation detail, not part of any specification.