Algo VisualizedStart learning

Prefix Function & KMP

KMP finds every occurrence of a pattern while reading each text character essentially once, with no hashing and no luck involved. Its prefix function is also the key to borders, periods and many other string puzzles.

advanced⏱ 15 min read

←Builds on

11Naive Pattern MatchingKMP removes the naive matcher's habit of stepping back in the text.101-D DP: Coins & LISThe prefix function is filled left to right, each value built from earlier ones.5Trie & AutocompleteThe prefix function acts like failure links in a trie of the pattern: on a mismatch, fall back to the longest border.

Leads to→

+Z-FunctionThe Z-function measures matches with the string's start, just as the prefix function measures borders.
1Learn2Play3Check4Practice
01

Learn

The idea, the mechanics and the cost.

01Borders and the prefix function

A border of a string is a proper prefix that is also a suffix. In ABAB, the string AB is both how it starts and how it ends.

The prefix function stores, for every position i of the pattern, the length of the longest border of P[0..i]:

π[i] = longest proper prefix of P[0..i] that is also its suffix

For ABABC you get π = [0, 0, 1, 2, 0]. Why care? If you matched ABAB and then fail, the last two characters you read (AB) are already the first two characters of the pattern. You can keep them instead of starting over. That one observation drives the whole algorithm.

prefixsuffixA0B1A2B3C4π00120pat[0..3] = ABAB: border "AB", so π[3] = 2

02The KMP scan

KMP walks the text with a pointer i and keeps j, the number of pattern characters currently matched.

  • If T[i] = P[j]: increase j, move i on.
  • If they differ and j > 0: set j = π[j−1] and compare T[i] again. This slides the pattern right while keeping the matched border.
  • If they differ and j = 0: just move i on.
  • If j = m: report an occurrence at i − m + 1, then set j = π[m−1] to catch overlapping matches.

The text pointer i never moves backward. That one property is what makes KMP fast.

mismatch: A ≠ C, j = 4ABABABCABABCABABCj = π[3] = 2: "AB" is already matchedABABABCABABCABABCi stays putshift = j − π[j−1] = 4 − 2 = 2
The pattern jumps two places, but the text pointer stays on the same character.

03Building π with the same idea

You compute π by running the same logic on the pattern against itself. Keep k = π[i−1], the current border length. To extend it to position i, compare P[i] with P[k]:

  • equal: π[i] = k + 1
  • different and k > 0: fall back to the next shorter border, k = π[k−1], and try again
  • different and k = 0: π[i] = 0

This is dynamic programming over the pattern: each value reuses earlier ones. The build costs O(m) and the scan O(n), because j can drop at most as many times as it grew. Together that is O(n + m) in the worst case.

n = 1000, m = 100, text AAAA…, pattern AA…ABnaive≈ 90 100KMP≤ 2 000 comparisons(n − m + 1)·m vs ≤ 2n

04When to reach for KMP

For a single search in normal text, your language's own find is fine. Reach for KMP when:

  • you need a guaranteed O(n + m), for example on adversarial contest tests
  • the text arrives as a stream and you cannot go back
  • the question is really about the pattern itself: its shortest period is m − π[m−1], and its borders are π[m−1], π[π[m−1]−1], …

A common trick: run the prefix function on P + "#" + T, where # appears in neither string. Every position with π = m marks an occurrence. Then you do not even need separate scan code: building π is enough.

Cost at a glance

Build πO(m)
Scan the textO(n)
Total, worst caseO(n + m)
MemoryO(m)

Remember

  1. π[i] is the length of the longest border (prefix = suffix) of the pattern prefix ending at i.
  2. On a mismatch KMP sets j = π[j−1] and keeps the text pointer where it is, so i never moves back.
  3. KMP is O(n + m) even in the worst case, and π also gives borders and periods of a string.
02

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: First π is built. Then, during the scan, watch the highlighted text character: it only ever moves right, while the pattern jumps.

Interactive visualizerfocus here, then space ← →
✎ Your inputText up to 16 characters, pattern up to 6. Repetitive patterns like ABAB or AAB make π interesting.

Prefix function & KMP

ABABC

pattern "ABABC" · π

ABABC
π0····
KMP first builds π, where π[i] = length of the longest proper prefix of pat[0..i] that is also a suffix. This is DP over the pattern.

Pseudocode

 1 π[0] = 0 2   while k>0 and pat[i]≠pat[k]: k = π[k-1]   // fall back 3   if pat[i]==pat[k]: k++;  π[i] = k 4 scan: j = matched length so far 5   on mismatch with j>0: j = π[j-1]   (keep the border, no reread) 6   on match: advance both; i never moves backward 7   when j == m: report occurrence
1 / 1
03

Check

Three questions. Pick an answer to see why.

Q1

What is the prefix function of "AABAA"?

Q2

Pattern ABABC (π = 0,0,1,2,0). You matched ABAB (j = 4) and the next text char is A. What is the new j?

Q3

Why is the KMP scan O(n) even though it contains a while loop?

04

Practice

Real problems to lock it in, easiest first.

LeetCodeFind the Index of the First Occurrence in a String beginner↗CSESFinding Borders intermediate↗CSESFinding Periods intermediate↗LeetCodeLongest Happy Prefix advanced↗LeetCodeShortest Palindrome advanced↗