Visualizer CodeViz · Algorithms, visualized

Part II · Substring search · week 6

Knuth–Morris–Pratt

Precompute, for every state and character, where a mismatch leaves you. Then read the text once, never backing up — linear, guaranteed.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

search≤ n character accesses
DFA buildO(R·m)
backupnever — works on a stream
worst caselinear

Reference: Sedgewick & Wayne, §5.3; Knuth–Morris–Pratt 1977.

Knuth–Morris–Pratt in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def build_dfa(pat):
    # dfa[r][j] = state to be in after seeing alphabet letter r in state j.
    # State j means 'the last j characters of the text matched pat[0..j-1]'.
    # X is the state we would be in had the match started one character
    # later -- that is what makes the mismatch cases free.
    # The alphabet is the pattern's OWN characters: any other character
    # sends the automaton back to state 0, so its row would be all zeros.
    # (Sedgewick's Java indexes by ord(c) over all R = 256 bytes; that is
    #  the same table with 250 empty rows.)
    alpha = sorted(set(pat))
    col = {c: r for r, c in enumerate(alpha)}
    m = len(pat)
    dfa = [[0] * m for _ in alpha]
    dfa[col[pat[0]]][0] = 1
    x = 0
    for j in range(1, m):
        for r in range(len(alpha)):
            dfa[r][j] = dfa[r][x]         # copy the MISMATCH cases from X
        dfa[col[pat[j]]][j] = j + 1       # then set the one MATCH case
        x = dfa[col[pat[j]]][x]           # and slide X along
    return dfa, col

def search(pat, txt):
    dfa, col = build_dfa(pat)
    m, n = len(pat), len(txt)
    i = j = 0
    while i < n and j < m:
        c = txt[i]
        j = dfa[col[c]][j] if c in col else 0   # one lookup per character
        i += 1                            # i NEVER goes backwards
    return i - m if j == m else n

Why it works

What a state means

State j means: the last j characters of the text read so far are exactly pat[0..j-1]. Reaching state m is a match. The search loop is then trivial — one table lookup per text character, and i only ever increases. All the difficulty has been moved into building the table.

The X trick

X is the state the automaton would be in if the current match attempt had started one character later. On a mismatch in state j, that is precisely where you belong — so dfa[c][j] = dfa[c][X] copies every mismatch transition in one line, and only the single matching character needs a real decision. Then X advances by taking its own transition on pat[j].

This is the part worth stepping through slowly. It is also why the construction is O(R·m) rather than O(m2).

Never backing up

The reason KMP matters is not the constant factor — brute force is often faster in practice. It is that i never decreases, so the text can be consumed as a stream: no buffer, no rewind, constant memory beyond the DFA. That is what you need for a grep over a pipe, a network intrusion detector, or a tape.

History

Knuth, Morris and Pratt discovered this independently around 1976 while Cook was proving that a certain automaton model could recognise these patterns in linear time — theory predicted the algorithm before anyone found it. It is a good story about the practical value of lower-bound theory, and the paper's authors were themselves surprised the construction was so simple.

What to try in the animation

The table below is the DFA. Only characters that occur in the pattern are shown — every other character sends the automaton back to state 0.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Knuth–Morris–Pratt in the player →

The rest of Substring search