Knuth-Morris-Pratt and the prefix function

The Knuth-Morris-Pratt algorithm, KMP for short, finds every occurrence of a pattern of length m in a text of length n in O(n + m) time, and it never moves back in the text. It first computes the prefix function of the pattern: pi[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it, called its longest border. During the search, a mismatch after j matched characters does not send the pattern back to the start: the last pi[j − 1] characters read are already a prefix of the pattern, so the search continues from there. Knuth, Morris and Pratt published the method in 1977, and the ACM, IEEE and AAAI computing curricula of 2023 name it, with Boyer-Moore, as an example of efficient string matching. This lesson builds the table step by step, traces a search and counts the work saved.

Where the direct search wastes work

The direct search tries every start and, after a mismatch, slides the pattern one place and compares again from its first character, so it reads the same text characters over and over. Search for 199 copies of a and then b in a text of 20,000 copies of a: every start matches 199 characters before it fails, and the next start reads 198 of them again. The run below counts the comparisons of both methods on the previous lesson’s texts:

# Character comparisons of the direct search and of KMP on the same three texts. The direct search starts again one
# place further on after every mismatch and reads those characters again; KMP reads each text character once and
# compares it at most a few times.
import random


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]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi


def direct(text, pattern):
    n, m = len(text), len(pattern)
    found, compared = [], 0
    for i in range(n - m + 1):
        k = 0
        while k < m:
            compared += 1
            if text[i + k] != pattern[k]:
                break
            k += 1
        if k == m:
            found.append(i)
    return found, compared


def kmp(text, pattern):
    pi, m = prefix_function(pattern), len(pattern)
    found, compared, j = [], 0, 0
    for i, c in enumerate(text):
        while True:  # every comparison of c with a pattern character is counted once
            compared += 1
            if c == pattern[j]:
                j += 1
                break
            if j == 0:
                break
            j = pi[j - 1]
        if j == m:
            found.append(i - m + 1)
            j = pi[m - 1]
    return found, compared


rng = random.Random(5)
cases = [
    ("random DNA, n = 20,000, m = 200", "".join(rng.choices("ACGT", k=20_000)), "".join(rng.choices("ACGT", k=200))),
    ("a * 20,000 against a * 199 + b", "a" * 20_000, "a" * 199 + "b"),
    ("a * 20,000 against a * 200", "a" * 20_000, "a" * 200),
]
for name, text, pattern in cases:
    (f1, c1), (f2, c2) = direct(text, pattern), kmp(text, pattern)
    assert f1 == f2
    print(f"{name}: {len(f1):,} occurrences; direct search {c1:,} comparisons, KMP {c2:,} (2n = {2 * len(text):,})")

random DNA, n = 20,000, m = 200: 0 occurrences; direct search 26,308 comparisons, KMP 24,938 (2n = 40,000)
a * 20,000 against a * 199 + b: 0 occurrences; direct search 3,960,200 comparisons, KMP 39,801 (2n = 40,000)
a * 20,000 against a * 200: 19,801 occurrences; direct search 3,960,200 comparisons, KMP 20,000 (2n = 40,000)

On the second text the direct search makes 3,960,200 comparisons and KMP 39,801. On the third, where the pattern occurs at all 19,801 starts, KMP needs 20,000 comparisons, one per character, while Rabin-Karp had to verify every occurrence in full. Knuth-Morris-Pratt stays within 2n comparisons on every input, because it remembers how much of the pattern matched.

The prefix function, step by step

A border of a string is a proper prefix that is also a suffix: “ab” is a border of “abab”, and “” is a border of every string. The prefix function stores, for every prefix of the pattern, the length of its longest border:

It is computed from left to right. To find pi[i], take k = pi[i − 1], the longest border of the previous prefix, and try to grow it by one character: when p[i] equals p[k], pi[i] = k + 1. When they differ, the table tries the next shorter border, pi[k − 1], which is a border of the border, and keeps stepping down until one grows or k is 0. Run the trace and change the patterns to see every fallback:

# The prefix function, built one position at a time. pi[i] is the length of the longest proper prefix of p[0..i]
# that is also a suffix of it. Change PATTERNS and run again to trace your own strings.
PATTERNS = ["ababcabab", "aabaaab"]


def prefix_function(p, trace=False):
    pi = [0] * len(p)
    for i in range(1, len(p)):
        k = pi[i - 1]  # the longest border of p[0..i-1]: try to extend it by p[i]
        steps = []
        while k > 0 and p[i] != p[k]:
            steps.append(f"p[{k}]={p[k]} ≠ {p[i]}, fall back to pi[{k - 1}]={pi[k - 1]}")
            k = pi[k - 1]
        if p[i] == p[k]:
            steps.append(f"p[{k}]={p[k]} = {p[i]}, extend to {k + 1}")
            k += 1
        else:
            steps.append(f"p[{k}]={p[k]} ≠ {p[i]}, no border")
        pi[i] = k
        if trace:
            print(f"  i={i} {p[i]}: start at k={pi[i - 1]}; " + "; ".join(steps) + f" → pi[{i}] = {k}")
    return pi


for p in PATTERNS:
    print(f"pattern {p}")
    pi = prefix_function(p, trace=True)
    print(f"  pi = {pi}")

pattern ababcabab
  i=1 b: start at k=0; p[0]=a ≠ b, no border → pi[1] = 0
  i=2 a: start at k=0; p[0]=a = a, extend to 1 → pi[2] = 1
  i=3 b: start at k=1; p[1]=b = b, extend to 2 → pi[3] = 2
  i=4 c: start at k=2; p[2]=a ≠ c, fall back to pi[1]=0; p[0]=a ≠ c, no border → pi[4] = 0
  i=5 a: start at k=0; p[0]=a = a, extend to 1 → pi[5] = 1
  i=6 b: start at k=1; p[1]=b = b, extend to 2 → pi[6] = 2
  i=7 a: start at k=2; p[2]=a = a, extend to 3 → pi[7] = 3
  i=8 b: start at k=3; p[3]=b = b, extend to 4 → pi[8] = 4
  pi = [0, 0, 1, 2, 0, 1, 2, 3, 4]
pattern aabaaab
  i=1 a: start at k=0; p[0]=a = a, extend to 1 → pi[1] = 1
  i=2 b: start at k=1; p[1]=a ≠ b, fall back to pi[0]=0; p[0]=a ≠ b, no border → pi[2] = 0
  i=3 a: start at k=0; p[0]=a = a, extend to 1 → pi[3] = 1
  i=4 a: start at k=1; p[1]=a = a, extend to 2 → pi[4] = 2
  i=5 a: start at k=2; p[2]=b ≠ a, fall back to pi[1]=1; p[1]=a = a, extend to 2 → pi[5] = 2
  i=6 b: start at k=2; p[2]=b = b, extend to 3 → pi[6] = 3
  pi = [0, 1, 0, 1, 2, 2, 3]

At i = 4 the character c fails to extend “ab”, falls back to the empty border and gets 0. In “aabaaab”, position 5 falls back from 2 to 1 before it extends. The table costs O(m) time, because k rises by at most one per position and every fallback lowers it. One value says even more: m − pi[m − 1] is the smallest period of the pattern, the smallest shift under which it agrees with itself, so “abcabcab”, with pi[7] = 5, has period 3.

Searching without moving back

The search keeps j, the number of pattern characters that match the text read so far. Each text character either extends the match, or j falls back along the same chain of borders until the character fits or j is 0. After a full match the search continues from pi[m − 1], so overlapping occurrences are found too.

# Knuth-Morris-Pratt search: j is how many pattern characters match the text read so far. On a mismatch j falls back
# to pi[j - 1], the longest border of what matched, and the text index never moves back.
import random


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]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi


def kmp_search(text, pattern, trace=False):
    """Start index of every occurrence of pattern in text, overlapping ones included (pattern not empty)."""
    pi = prefix_function(pattern)
    m, j, found = len(pattern), 0, []
    for i, c in enumerate(text):
        chain = [j]
        while j > 0 and c != pattern[j]:
            j = pi[j - 1]  # keep the longest border of the matched part
            chain.append(j)
        if c == pattern[j]:
            j += 1
        if trace:
            fell = f", after falling back {' → '.join(map(str, chain))}" if len(chain) > 1 else ""
            print(f"  text[{i}] = {c}: j = {j}{fell}" + (f": match at {i - m + 1}, j becomes pi[{m - 1}] = {pi[m - 1]}" if j == m else ""))
        if j == m:
            found.append(i - m + 1)
            j = pi[m - 1]
    return found


print("pi of abab:", prefix_function("abab"))
print("search abab in abacababab:")
print(kmp_search("abacababab", "abab", trace=True))

rng = random.Random(1)
for _ in range(2_000):
    text = "".join(rng.choices("ab", k=rng.randint(0, 30)))
    pattern = "".join(rng.choices("ab", k=rng.randint(1, 6)))
    assert kmp_search(text, pattern) == [i for i in range(len(text)) if text.startswith(pattern, i)]
print("2,000 random texts: the same occurrences as checking every start")

pi of abab: [0, 0, 1, 2]
search abab in abacababab:
  text[0] = a: j = 1
  text[1] = b: j = 2
  text[2] = a: j = 3
  text[3] = c: j = 0, after falling back 3 → 1 → 0
  text[4] = a: j = 1
  text[5] = b: j = 2
  text[6] = a: j = 3
  text[7] = b: j = 4: match at 4, j becomes pi[3] = 2
  text[8] = a: j = 3
  text[9] = b: j = 4: match at 6, j becomes pi[3] = 2
[4, 6]
2,000 random texts: the same occurrences as checking every start

At text[3] the character c breaks a match of “aba”: j falls back 3 → 1 → 0, and the text index stays where it is. After the match at 4, j becomes pi[3] = 2, so the next two characters complete the overlapping match at 6. Every fallback lowers j, and j rises at most once per text character, so the search makes at most about 2n comparisons and costs O(n) after the O(m) table.

Two further tools come from the same table. A refined table skips a border when the character after it equals the one that just failed, which limits the work spent on a single text character. And the chain of borders lists every border of a string, which gives its periods and tells whether it is a shorter string repeated.

Practise and check yourself

Count overlapping occurrences and find the smallest period. The tests compare your answers with direct checks on random strings and use texts of 200,000 characters.

def count_occurrences(text, pattern):
    """How many times pattern occurs in text, overlapping occurrences included, found with KMP."""
    # Replace this line with your code.
    return 0


def smallest_period(s):
    """The smallest p >= 1 with s[i] == s[i + p] wherever both exist."""
    # Replace this line with your code.
    return len(s)

import random

from kmp_tools import count_occurrences, smallest_period


def direct_count(text, pattern):
    return sum(text.startswith(pattern, i) for i in range(len(text)))


def direct_period(s):
    return next(p for p in range(1, len(s) + 1) if all(s[i] == s[i + p] for i in range(len(s) - p)))


def test_small_cases():
    """overlapping occurrences and periods of short strings"""
    assert count_occurrences("aaaa", "aa") == 3
    assert count_occurrences("abacababab", "abab") == 2
    assert count_occurrences("abc", "abcd") == 0
    assert count_occurrences("", "a") == 0
    assert smallest_period("abcabcab") == 3
    assert smallest_period("abcd") == 4
    assert smallest_period("aaaa") == 1
    assert smallest_period("abaab") == 3
    assert smallest_period("x") == 1


def test_random_strings():
    """500 random strings over two letters, against direct checks"""
    rng = random.Random(6)
    for _ in range(500):
        text = "".join(rng.choices("ab", k=rng.randint(0, 40)))
        pattern = "".join(rng.choices("ab", k=rng.randint(1, 6)))
        assert count_occurrences(text, pattern) == direct_count(text, pattern), (text, pattern)
        s = "".join(rng.choices("ab", k=rng.randint(1, 20)))
        assert smallest_period(s) == direct_period(s), s


def test_long_inputs():
    """200,000 characters: a repeated letter, and a period found in one pass"""
    assert count_occurrences("a" * 200_000, "a" * 1_000) == 199_001
    assert count_occurrences("ab" * 100_000, "abba") == 0
    assert smallest_period("abc" * 66_666 + "ab") == 3
    assert smallest_period("a" * 199_999 + "b") == 200_000

/** How many times pattern occurs in text, overlapping occurrences included, found with KMP. */
export function countOccurrences(text, pattern) {
  // Replace this line with your code.
  return 0;
}

/** The smallest p >= 1 with s[i] === s[i + p] wherever both exist. */
export function smallestPeriod(s) {
  // Replace this line with your code.
  return s.length;
}

import { test, assert } from 'mysmartcopilot:test';
import { countOccurrences, smallestPeriod } from './kmp_tools.mjs';

function directCount(text, pattern) {
  let n = 0;
  for (let i = 0; i < text.length; i++) if (text.startsWith(pattern, i)) n++;
  return n;
}

function directPeriod(s) {
  for (let p = 1; p <= s.length; p++) {
    let ok = true;
    for (let i = 0; i + p < s.length && ok; i++) ok = s[i] === s[i + p];
    if (ok) return p;
  }
  return s.length;
}

function makeRandom(seed) {
  return () => (seed = (seed * 48271) % 2147483647) / 2147483647;
}

function randomWord(random, min, max) {
  const n = min + Math.floor(random() * (max - min + 1));
  let s = '';
  for (let i = 0; i < n; i++) s += random() < 0.5 ? 'a' : 'b';
  return s;
}

test('overlapping occurrences and periods of short strings', () => {
  assert.equal(countOccurrences('aaaa', 'aa'), 3);
  assert.equal(countOccurrences('abacababab', 'abab'), 2);
  assert.equal(countOccurrences('abc', 'abcd'), 0);
  assert.equal(countOccurrences('', 'a'), 0);
  assert.equal(smallestPeriod('abcabcab'), 3);
  assert.equal(smallestPeriod('abcd'), 4);
  assert.equal(smallestPeriod('aaaa'), 1);
  assert.equal(smallestPeriod('abaab'), 3);
  assert.equal(smallestPeriod('x'), 1);
});

test('500 random strings over two letters, against direct checks', () => {
  const random = makeRandom(6);
  for (let t = 0; t < 500; t++) {
    const text = randomWord(random, 0, 40);
    const pattern = randomWord(random, 1, 6);
    assert.equal(countOccurrences(text, pattern), directCount(text, pattern), `${text} ${pattern}`);
    const s = randomWord(random, 1, 20);
    assert.equal(smallestPeriod(s), directPeriod(s), s);
  }
});

test('200,000 characters: a repeated letter, and a period found in one pass', () => {
  assert.equal(countOccurrences('a'.repeat(200_000), 'a'.repeat(1_000)), 199_001);
  assert.equal(countOccurrences('ab'.repeat(100_000), 'abba'), 0);
  assert.equal(smallestPeriod('abc'.repeat(66_666) + 'ab'), 3);
  assert.equal(smallestPeriod('a'.repeat(199_999) + 'b'), 200_000);
});

Why KMP is correct and linear, with every comparison counted Pro: opens with a Pro, Premium or Ultimate pass

Borders, periods and repeated phrases, proved and counted Pro: opens with a Pro, Premium or Ultimate pass

KMP in five languages, and three bugs that pass small tests Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• The prefix function gives, for each prefix of the pattern, the length of its longest proper prefix that is also a suffix, and it is computed in O(m) by extending or falling back along borders.
• KMP keeps the number of matched characters; on a mismatch it falls back to pi[j − 1] and never moves back in the text, so the search costs O(n + m).
• After a full match, continue from pi[m − 1], or overlapping occurrences are lost.
• m − pi[m − 1] is the smallest period of a string of length m.