Hard · KMP Prefix Function
Understand → Visualise → Practice.
Return the first index where `pattern` occurs in `text`, or −1 when it is absent. An empty pattern starts at index 0.
The prefix function (LPS) tells you, for each pattern prefix, the longest proper prefix that is also a suffix. After a mismatch, jump the pattern pointer back to it instead of moving the text pointer back.
lps[i] = length of the longest proper prefix of pattern[:i + 1] that is also its suffix.
On a mismatch, set j = lps[j − 1] until characters match or j = 0; on a match, advance j.
When j reaches the pattern length, the match starts at i − len(pattern) + 1.
O(n + m) time and O(m) space.
Falling back with the text index loses KMP's linear-time guarantee.
Read the full guide first: Strings: Frequencies, Matching and Palindromes.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.