AlgoVerse

Knuth–Morris–Pratt (KMP)

String matching in O(n + m): no text character is read twice; after a mismatch, the prefix function says how far the pattern moves.

After a mismatch the naive method moves the pattern by one and compares from the start again. But we already know that the last q text characters matched P[0..q−1]. So:

Read the full explanation ↓
Input:
T="bacbabababab…" · P="ababa"PDF export

The pattern ababa occurs three times in bacbababababa, at shifts 4, 6 and 8; after the first match KMP keeps the overlap instead of starting over.

  1. def kmp_match(T, P):
  2. n, m = len(T), len(P)
  3. pi = prefix_function(P)
  4. matches = []
  5. q = 0 # how many characters of P match the text ending here
  6. shift = 0 # where P sits under T, for the picture
  7. for i in range(n):
  8. while q > 0 and P[q] != T[i]:
  9. q = pi[q - 1]
  10. if P[q] == T[i]:
  11. q = q + 1
  12. if q == m:
  13. matches.append(i - m + 1)
  14. q = pi[q - 1]
  15. shift = i - q + 1
  16. return matches
  19. def prefix_function(P):
  20. pi = [0] * len(P)
  21. k = 0
  22. for q in range(1, len(P)):
  23. while k > 0 and P[k] != P[q]:
  24. k = pi[k - 1]
  25. if P[k] == P[q]:
  26. k = k + 1
  27. pi[q] = k
  28. return pi

Invariant: After each step, P[0..q−1] is the longest prefix of P that ends T[0..i].

Start

0123456789101112
bacbababababa
ababa
pi—
matches—

Local variables

T'bacbababababa'
P'ababa'

Orange = changed in this step

Call stack

  1. kmp_match()line 1
Step 1 of 115
Black = match_char, fall_back · Orange = key stepmatch_char: 0/10 · fall_back: 0/1 · found: 0/3
    Explanation

    The idea

    After a mismatch the naive method moves the pattern by one and compares from the start again. But we already know that the last q text characters matched P[0..q−1]. So:

    • if T[i] matches P[q], q grows by one;
    • if not, set q to π[q − 1] (the longest border of the matched part) and try again; the text is not re-read;
    • if q = m, the pattern is found; go on with q = π[m − 1] so overlapping occurrences are found too.

    Cost

    i only moves forward and each fall-back shrinks q; so the whole job is O(n), plus O(m) to build π.

    What to watch in the trace

    • The i pointer only moves forward over the text; the pattern is drawn at its current shift and its filled cells have matched.