Knuth–Morris–Pratt

searching for a needle without ever going back in the haystack

ALG 13.2 · ADS2

The problem

• Haystack σ (length S), needle ι (length J). Report all k with σ[k : k+J] = ι.
• Trying every start: Θ(JS).
• "Compare, and on a mismatch continue from where you are" is wrong:
  σ = c o c o c o a, ι = cocoa
  we read coco, then c ≠ a … but an occurrence starts inside what we already read.
• Going back in σ fixes it but costs Θ(JS) again.

Incremental view

• Read σ one character at a time.
• Keep the state α = the longest prefix of ι that is a suffix of the text read so far.
• Whenever α = ι, report an occurrence.

Question: when the next character does not fit, where do we go? E.g. state coco + c → coc. Why?

The picture: live alignments

Place a copy of the needle at every position where it can still become an occurrence, i.e. it agrees with everything read so far.

After reading cococ. Green = already matched, grey = still to come. Each live alignment is a prefix of ι that is a suffix of the text read so far.

Key observation

Every live alignment lies inside the window of the top one, so each of them is a suffix of α.

• z(α) = the longest proper suffix of α that is a prefix of ι = the next row down in the stack.
• The whole stack is determined by α alone. We can forget σ.
• z depends only on the needle, so we can precompute it: the failure edges of the automaton.

Reading the next character x

• Each live alignment either expects x (it survives and gets one longer) or it does not (it dies, forever).
• New state = the topmost survivor, one longer. (If nobody survives: ε.)
• So: walk down the stack α, z(α), z(z(α)), … until somebody expects x.

Rows below the topmost survivor need not be checked: the ones that survive are exactly the stack of the new state.

Demo: ι = cocoa, σ = cococoa

Demo: ι = abracadabra (several failure edges in one step, overlapping occurrences)

Running time

• Each character: at most one forward edge (state +1).
• Each failure edge: state −1 or more. The state never goes below 0.
• ⇒ #failure edges ≤ #forward edges ≤ S.

In the picture: a row can only die once, and each character adds at most one row (ε).

Building the automaton

• States 0 … J and forward edges: trivial.
• Failure edges: we need Z[i] = |z(ι[:i])| for i = 1, …, J.
• Trying all suffixes of all prefixes is slow.

Bite off the first character

• Running on α: the stack is α, z(α), z(z(α)), …
• Running on α[1:]: the same stack without the top row. The alignment starting at position 0 never existed, because we never read position 0.
• So the final state after reading α[1:] is the longest proper suffix of α that is a prefix of ι, i.e. z(α).

Formally: this is just the invariant of KmpSearch, applied to the text α[1:].

One run is enough

• Z[i] = state after reading ι[1:i].
• ι[1:2], ι[1:3], …, ι[1:J] are all prefixes of ι[1:].
• ⇒ run the automaton once on ι[1:] and record the state after each character.

But we don't have the automaton yet!

• When we compute Z[i], we have read i − 1 characters, so the state is at most i − 1.
• Walking down from state s only uses Z[s], Z[Z[s]], …, with indices < i: already written.
• The reader is always behind the writer: it only uses failure edges that are already built.

Baron Munchausen pulled himself out of a swamp by his own bootstraps (ALG, footnote in 13.2).

Demo: building Z for ι = abracadabra

KmpBuild

• It is KmpSearch on a text of length J − 1 ⇒ Θ(J).

Bonus: Fibonacci strings, deep failure chains (ι = abaababaabaab)

One character can cause up to about log_φ J failure edges, and the Fibonacci strings reach this bound (Knuth, Morris, Pratt 1977, §5). Playground: try your own strings · Failure Function Sprint · ADS2 Arcade