Sign in to watch this lesson
Algorithms - Strings · 5:04
Prefix Function and KMP
The prefix function stores, for every prefix of a string, the length of its longest border (a proper prefix that is also a suffix). We build it cell by cell for aabaaab, watch a mismatch fall back to the border of the border, and prove the loop linear with a meter that can only fall as far as it has risen. Knuth-Morris-Pratt is then just the prefix function of pattern + '#' + text: a deterministic O(n + m) matcher that reads the text once and can stream it.
You will learn
- Define a border and the prefix function pi[i], and compute it by hand for short strings such as abcabcd and aabaaab
- Explain the fallback j = pi[j-1]: a border of the current border is the next candidate, so no strings are compared
- Prove the O(n) running time with the amortized argument (j rises at most n times, so it falls at most n times)
- Use pi of pattern + '#' + text to find every occurrence in O(n + m), streaming the text with O(n) memory, and avoid the separator and off-by-one traps