TRT
Sign in

Advanced · Module 19 · Lesson 3 of 4

KMP and prefix functions

The prefix function records, for every position of a pattern, the longest proper prefix that is also a suffix there. Knuth-Morris-Pratt uses it to search a text without ever moving backward, in O(n + m) time in the worst case.

Pro — members onlyAbout 15 minutes

By the end you can

  • Compute the prefix function of a string in linear time, and explain the fallback step
  • Search a text with KMP in O(n + m), including overlapping matches
  • Use prefix functions for periodicity and palindrome problems

Builds on Rolling hash and Rabin-Karp, Dynamic arrays and growth.

01 · A question first

Searching for aaaab in a text of a million a's, the simple algorithm matches four characters, fails on the fifth, shifts by one and starts over: four million comparisons for nothing. Every failed attempt already knew what the next four characters were. How can a search reuse what it has matched instead of reading it again?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • The waste in simple search
  • Borders and the prefix function
  • Computing it in linear time
  • Searching a text
  • The prefix function beyond search
  • Relatives in the real world
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · easy · LeetCodeRepeated substring patternDecide whether a string is a shorter block repeated several times, using its smallest period from the prefix function.Practice · hard · LeetCodeShortest palindromeAdd the fewest characters to the front of a string to make it a palindrome, by finding its longest palindromic prefix with the prefix function.Practice · easy · LeetCodeFind the first occurrence in a stringReturn the first index where a pattern occurs in a text, with Rabin-Karp or KMP in linear time.

Asked in interviews

Something wrong with this lesson? Report a problem