---
title: Knuth–Morris–Pratt
source: 'https://academia.sh/en/courses/algorithms/knuth-morris-pratt'
course: Algorithms
language: en
updated: '2026-08-17T18:07:47+00:00'
license: 'CC BY-SA 4.0'
---

# Knuth–Morris–Pratt

The definition of the prefix function and its linear computation, search that never backtracks in the text, amortized cost analysis, and string periodicity.

Brute-force search wasted effort by forgetting the matches made before a mismatch.
Rabin–Karp reduced this waste with a hash but never used the pattern's **structure** at
all.

The idea of the Knuth–Morris–Pratt algorithm is this: if the matched part is already
known, the pattern's own internal repetition tells us how many positions can safely be
skipped.

## The Observation

Consider comparing the pattern `ABABCABAB` against the text, where the first four
characters (`ABAB`) matched and the fifth did not. It is known **for certain** that the
text contains `ABAB` at that position.

Brute force shifts by one position and tests the text's `BAB…` portion from scratch. Yet
the `AB` prefix of `ABAB` is also its `AB` suffix; the search can therefore continue
after shifting by two positions, without retesting the pattern's first two characters.
The intermediate positions are not worth trying, because what characters are there is
already known.

The general rule: the longest piece that is **both a prefix and a suffix** of the
matched prefix is kept, the rest is discarded.

## The Prefix Function

The **prefix function** $\pi$ gives, for every prefix of the pattern, "the length of the
longest piece that is both a proper prefix and a suffix." "Proper" here means the piece
cannot be the whole prefix itself.

```python
def prefix_function(pattern: str) -> list[int]:
    """pi[i]: the longest proper prefix-suffix length of pattern[0..i]."""
    pi = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]                  # fall back to a shorter candidate prefix
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    return pi


print(prefix_function("ABABCABAB"))       # [0, 0, 1, 2, 0, 1, 2, 3, 4]
print(prefix_function("AABAACAABAA"))     # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
print(prefix_function("ABCDE"))           # [0, 0, 0, 0, 0]
```

The values read directly: the longest prefix–suffix overlap of the entire pattern
`ABABCABAB` is 4 (`ABAB`); for the `ABAB` piece up to its fourth character it is 2
(`AB`); for `ABCDE`, which contains no repetition at all, every value is zero.

The computation itself is searching the pattern within itself: the variable `k` holds
the length of the prefix matched so far and falls back to a shorter candidate on a
mismatch. The cost is $O(m)$ — the reasoning is the same as in the search, and is given
in the next section.

## The Search

The search applies the same fallback logic to the text. The text cursor **never moves
backward**; only the pattern cursor falls back.

```python
def kmp(text: str, pattern: str) -> tuple[list[int], int]:
    """(positions, character-comparison count)"""
    pi = prefix_function(pattern)
    positions: list[int] = []
    k = 0
    count = 0
    for i, character in enumerate(text):
        while k > 0 and character != pattern[k]:
            count += 1
            k = pi[k - 1]
        count += 1
        if character == pattern[k]:
            k += 1
        if k == len(pattern):
            positions.append(i - len(pattern) + 1)
            k = pi[k - 1]                  # do not miss an overlapping next occurrence
    return positions, count


text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp(text, pattern))                  # ([10], 23)
print(kmp("ABABAB", "AB"))                 # ([0, 2, 4], 6)
print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51)
```

The last line is decisive: on the input where brute force made 231 comparisons, KMP
makes 51. The quadratic behavior has disappeared entirely.

Once a match is found, the assignment `k = pi[k-1]` ensures overlapping occurrences are
not missed. Searching for `ABAB` inside `ABABAB` finds both position 0 and position 2.

## Cost

Preprocessing is $O(m)$, search is $O(n)$, total $O(n + m)$ — in the **worst case**.
Extra space is $O(m)$ (the prefix-function table).

The reasoning is amortized; the total-cost method from the Method for Computing
Complexity lesson applies here directly.

The variable `k` increases by at most one on every turn; over $n$ turns, its total
increase is at most $n$. Every turn of the inner loop decreases `k` by at least one, and
`k` never goes negative. The inner loop can therefore run at most $n$ times in total.
Although the inner loop looks like $O(m)$ in isolation, its total cost across the whole
search is linear.

| Criterion | Brute force | Rabin–Karp | KMP |
|---|---|---|---|
| Preprocessing | None | $O(m)$ | $O(m)$ |
| Worst-case search | $O(nm)$ | $O(nm)$ | $O(n)$ |
| Extra space | $O(1)$ | $O(1)$ | $O(m)$ |
| Backtracks in text | Yes | No | No |

The last row produces a practical consequence: because the text cursor never moves
backward, the algorithm can run over a **stream** that is not entirely in memory.
Characters are processed as they arrive; no rewinding is needed.

## The Automaton View

The prefix function is, in fact, a compressed form of a **finite automaton**. Its states
hold the information "how many characters of the pattern have matched so far"; a
transition is defined for every character, and the final state signals a match.

If the transitions are precomputed, the fallback loop disappears from the search as
well: exactly one table lookup is made for every text character.

```python
def automaton(pattern: str, alphabet: str) -> list[dict[str, int]]:
    pi = prefix_function(pattern)
    m = len(pattern)
    transition: list[dict[str, int]] = [{} for _ in range(m + 1)]
    for state in range(m + 1):
        for character in alphabet:
            if state < m and character == pattern[state]:
                transition[state][character] = state + 1      # advance
            elif state == 0:
                transition[state][character] = 0              # back to start
            else:
                transition[state][character] = transition[pi[state - 1]][character]
    return transition


def search_with_automaton(text: str, pattern: str, alphabet: str) -> list[int]:
    transition = automaton(pattern, alphabet)
    m, state = len(pattern), 0
    positions: list[int] = []
    for i, character in enumerate(text):
        state = transition[state][character]
        if state == m:
            positions.append(i - m + 1)
    return positions


print(search_with_automaton("ABABDABACDABABCABAB", "ABABCABAB", "ABCD"))    # [10]
```

The cost is in memory: the table takes $O(m\sigma)$ space, and this is a serious cost
when the alphabet is large. The prefix function, by contrast, takes $O(m)$ space and
produces the same behavior amortized. The choice between the two approaches is made by
looking at alphabet size and search frequency.

## Periodicity

The prefix function directly gives one more piece of information besides the search: a
string's **smallest period**.

For a string of length $m$, the value $p = m - \pi[m-1]$ is the smallest period length.
If $m$ is exactly divisible by $p$, the string consists of repetitions of that piece.

```python
def smallest_period(string: str) -> tuple[int, bool]:
    pi = prefix_function(string)
    p = len(string) - pi[-1]
    return p, len(string) % p == 0


for example in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"):
    print(example, smallest_period(example))

# ABABAB (2, True)
# ABCABCABC (3, True)
# ABCD (4, True)
# AAAA (1, True)
```

For `ABCD` the period is the length itself: there is no repetition. This computation is
used in compression and in string-equivalence questions; the same table serves two
different purposes.

## Summary

- KMP uses the prefix–suffix overlap of the matched prefix to determine how many
  positions can be skipped on a mismatch.
- The prefix function gives, for every prefix, the longest proper prefix–suffix length,
  and is computed in $O(m)$.
- In the search, the text cursor never moves backward; only the pattern cursor falls
  back.
- Total cost is $O(n + m)$; the reasoning is amortized, bounding the total increase of
  the variable `k`.
- The absence of backtracking in the text makes the algorithm suitable for stream data.
- The same table also gives a string's smallest period.

## Next Step

KMP matches the pattern from start to end and looks at every text character at least
once. The next lesson takes up an approach that matches in the opposite direction:
comparison starting from the **end** of the pattern makes it possible to skip over some
text characters **without ever looking at them** on a mismatch, and produces
sublinear behavior in practice.