Algorithms · Lesson 7

KMP and the Prefix Function

Practice this topic →

The string matching problem

Given a pattern $P$ and a text $T$, decide whether $P$ is a factor of $T$, or find every occurrence.

The naive algorithm tries every starting position and compares $P$ against that factor, taking $O\left(mn\right)$ time.

Borders let us skip positions

Suppose we matched the first $j-1$ characters of $P$ against the text and then hit a mismatch. We already know the text looks like $P[1..j-1]$. A match can only start where a border of that matched prefix aligns:

In the lecture example, after matching 001100 and seeing a mismatch, the border 00 of 001100 tells us the next useful text position: shift past 01 and 11 at the start, resuming with the prefix 00 already matched.

The prefix function

The shift is always determined by the longest border of the already-matched prefix. Define

with $f_P\left(0\right)=0$.

The recurrence

Since each position adds $O\left(1\right)$ amortized work, the whole table costs $O\left(m\right)$ — and the matching pass that uses it is $O\left(n\right)$, so KMP runs in linear time.

Detecting unbordered words in linear time

The naive unbordered test compares every nonempty proper prefix against the same-length suffix, taking $O\left(n^2\right)$ time.

But notice: a word is unbordered exactly when its longest border is empty — that is, exactly when $f_w\left(\right|w\left|\right)=0$. Since the prefix function is computed in $O\left(n\right)$, we can test whether a word is unbordered in linear time.

All borders in linear time

The prefix function also lists every border of $w$ in $O\left(n\right)$ time. Start at the longest border and walk the failure chain:

Every entry is a border length, because the longest border of a border is again a border of the original word; and every border appears on this chain, since a border of length $j$ is the longest border of the $j$-th prefix of some chain entry. The chain strictly decreases and has at most $n$ entries, so all border lengths are enumerated in linear time.

The same chain counts, for every prefix $w[1..j]$, how many nonempty borders it has: its borders are its longest border together with the borders of that longest border, so

Each value is filled in one pass over the table, so all $n$ counts cost $O\left(n\right)$ time in total.

Practice

Prefix function values

Count the borders of a prefix

Find the occurrences

Practice this topic →Every quiz from this lesson, at four difficulties.