KMP failure function

50 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Find the pattern aabaaab inside the text aabaaabaaac. By hand you would line the pattern up at position 0, compare letter by letter, and if something fails, slide the pattern one step right and compare from the start again. Here the first alignment succeeds at once, but imagine the text is a long run of as with a b at the end and the pattern is aaab. Every alignment matches three letters and fails on the fourth; you slide one step and re-read the same as. For a text of n letters and a pattern of m, that is up to n × m comparisons: 10 million for a 10,000-letter text and a 1,000-letter pattern.

Build the structure, one piece at a time

The waste comes from forgetting. When the pattern fails at letter j, you already know the text matched the first j letters of the pattern. The pattern can be slid so that one of its own prefixes lines up with the end of that matched stretch, and the pattern alone tells you how far: nothing about the text is needed.

So build a table from the pattern alone, called lps (longest proper prefix that is also a suffix). lps[i] is the length of the longest prefix of p[0..i] that also ends at i, not counting the whole piece.

Now scan the text with two pointers, i in the text and j in the pattern. On a match, advance both. On a mismatch with j > 0, do not move i; set j = lps[j−1] and compare again. With j = 0, advance i. In the example all seven letters match, so the pattern is found at 0; set j = lps[6] = 3 and keep going. The text's next letters a a a match p[3..5], then c fails against p[6]: slide j to lps[5] = 2, fail again, j = lps[1] = 1, fail, j = lps[0] = 0, fail with nothing left, so advance i. The text pointer never moved backwards.

Why it is correct

The invariant: at every moment, p[0..j−1] equals the last j letters of the text read so far. After a mismatch, any alignment that could still succeed must have some prefix of the pattern matching a suffix of those j letters, and the longest such prefix is exactly lps[j−1] letters long, by the table's definition. Choosing the longest keeps every shorter possibility available for later slides, so no alignment is skipped. Since the matched letters are known to be equal to the pattern's own prefix, the slide can be computed from the pattern alone, which is why the table never looks at the text.

lps[i] = max { k < i+1 : p[0..k−1] = p[i−k+1..i] }

Why it is fast

During the scan, i only moves forward, so at most n advances. Each mismatch lowers j, and j can only have been raised by a match, one per advance of i, so there are at most n mismatches too. The scan is O(n). Building the table is the same argument on the pattern against itself: O(m). Total O(n + m), about 11,000 steps for the 10,000 and 1,000 case, against 10 million.

How to recognise it in an interview

Cues: find a pattern in a text, "does the string repeat", "shortest string to prepend to make a palindrome", borders of a string. Say: I will precompute the failure table of the pattern so that the text pointer never backs up. Find the Index of the First Occurrence in a String is the search itself. Repeated Substring Pattern is a one-liner on the table: the string repeats if n − lps[n−1] divides n. Shortest Palindrome builds the table of s + # + reverse(s) to find the longest palindromic prefix.

02The idea in one line

The prefix table lets a mismatch jump without re-scanning the text.

Reach for it when: Find first occurrence, shortest palindrome, repeated substring pattern.

Cost: O(n + m) time.

03The walk-through, step by step

The video works one example: KMP: 'aabaaab' in 'aabaaabaaac'. These are its captions in order, so you can follow without the video or check a step you missed.

1. First a table on the pattern alone: how far can a mismatch fall back?
2. lps[0..2]: 'a' → 0, 'aa' → 1 (prefix a = suffix a), 'aab' → 0
3. 'aaba' → 1, 'aabaa' → 2, 'aabaaa' → 2, 'aabaaab' → 3 ('aab')
4. Characters match: move both pointers forward
5. All 7 match: pattern found at 0; fall back to j = lps[6] = 3
6. 'a' = p[3]: match, j = 4
7. 'a' = p[4]: match, j = 5
8. 'a' = p[5]: match, j = 6
9. 'c' ≠ p[6]: slide j = lps[5] = 2, i stays
10. 'c' ≠ p[2]: slide j = lps[1] = 1, i stays
11. 'c' ≠ p[1]: slide j = lps[0] = 0, i stays
12. 'c' ≠ p[0] with nothing to fall back on: advance i
13. Text pointer never moves backwards: match at 0, scan done
14. Table O(m), scan O(n): O(n + m) instead of O(n·m)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in String Algorithms: Rolling hash (Rabin–Karp), Reverse-and-build string transforms, Parse with a state machine, Merge / compare two strings in lockstep, Multi-pattern scan with a set of lengths.