AlgoVerse

The KMP prefix function

For every prefix of the pattern, find the longest proper prefix that is also its suffix; with this table KMP knows how far to move after a mismatch.

A border of a string is a proper prefix that is also a suffix (for ababa: aba and a). π[q] is the length of the longest border of P[0..q].

Read the full explanation ↓
Input:
P="ababaca"PDF export

The pattern ababaca; π = (0, 0, 1, 2, 3, 0, 1).

  1. def prefix_function(P):
  2. # pi[q] = the length of the longest proper prefix of P[0..q] that is also a suffix of it.
  3. m = len(P)
  4. pi = [0] * m
  5. table = [list(P), pi]
  6. k = 0
  7. for q in range(1, m):
  8. while k > 0 and P[k] != P[q]:
  9. k = pi[k - 1]
  10. if P[k] == P[q]:
  11. k = k + 1
  12. pi[q] = k
  13. return pi

Invariant: Before round q, k equals π[q − 1]: P[0..k−1] is the longest prefix that also ends P[0..q−1].

Start

0123456
ababaca

The table is still empty.

Local variables

P'ababaca'

Orange = changed in this step

Call stack

  1. prefix_function()line 1
Step 1 of 39
Black = set_pi · Orange = key stepset_pi: 0/6 · extend: 0/4 · fall_back: 0/2
    Explanation

    The idea

    A border of a string is a proper prefix that is also a suffix (for ababa: aba and a). π[q] is the length of the longest border of P[0..q].

    Why it matters

    In KMP, when q characters of the pattern have matched and the next one does not, there is no need to start over: the longest border of the matched part is exactly what is still valid, so we fall back to π[q − 1].

    Computing it

    The table itself is built with the same idea: if P[k] = P[q] the border grows by one; otherwise fall back to the next shorter border π[k − 1] and try again.

    Cost

    k grows at most m times in all and each fall-back shrinks it; so the whole job is O(m) (amortized analysis).

    What to watch in the trace

    • The q and k pointers on the pattern; the table pairs each character with its π.