KMP Algorithm / LPS Array
KMP Algorithm / LPS Array: return the first index of needle in haystack — in O(n+m) via KMP.
- 1 <= haystack.length, needle.length <= 10⁴
- haystack and needle consist of only lowercase English characters.
Intuition
Find the index of the first occurrence in a string is substring search: return where needle first appears in haystack. The naive method compares the pattern at every position, and on inputs like a haystack of "aaaaaab" with needle "aaab" it re-examines almost the whole pattern at each shift, giving O(n·m).
The waste is specific and worth naming. When a mismatch occurs after matching k characters, those k characters are already known — they are a prefix of the pattern. Restarting from scratch throws that knowledge away.
KMP keeps it. The question it answers is: after matching k characters and failing, how much of that match is still usable? The answer is the length of the longest proper prefix of those k characters that is also a suffix of them — because a suffix of what was matched might be the start of the next occurrence.
That value, precomputed for every prefix length, is the LPS array:
- On a mismatch after j matched characters, fall back to lps[j−1] instead of 0, and never move the text pointer backwards.
The text pointer only advancing is what guarantees linearity. It moves forward at most n times, and j can only fall back as much as it has risen, so the total work is bounded by about 2n.
Building the LPS array uses the same fallback logic against the pattern itself, which is why the two halves of KMP look almost identical.
KMP. The insight is that a mismatch after a partial match doesn't require restarting — the matched prefix may itself end with a shorter prefix of the pattern, so you can slide forward without re-reading the text. The LPS array precomputes exactly how far to fall back, which is why the text pointer never moves backwards.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n + m) time and O(m) space.
See where naive search wastes work
On a mismatch the naive method restarts the pattern at the next position, re-comparing characters it already matched. KMP's entire gain is refusing to discard that knowledge, which is why understanding the waste comes first.
Define the LPS array
lps[i] is the length of the longest proper prefix of needle[0..i] that is also a suffix of it. Proper means it cannot be the whole string. This value says how much of a failed match can be salvaged as the start of a new one.
Build LPS with the same fallback rule
Walk the pattern with two pointers. On a match, extend and record; on a mismatch with len > 0, fall back to lps[len - 1] and retry without advancing the outer pointer. This is the same logic the search uses, applied to the pattern against itself.
Scan the text without backing up
Compare haystack[i] with needle[j]. On a match advance both. On a mismatch with j > 0, set j = lps[j-1] and leave i alone — that is the step the naive version cannot make. With j == 0, advance i.
Report a full match
When j reaches the needle's length, an occurrence ends at i, so it starts at i - j. Return that index for the first occurrence, or continue with j = lps[j-1] to find every occurrence.
Understand why it is linear
i only ever advances, at most n times. j increases at most once per step and can only fall back as much as it rose, so total pointer movement is bounded by 2n, giving O(n + m) time with O(m) space for the LPS array.
Solution & live demo
Common pitfalls
Restarting the text pointer after a mismatch
for i in range(len(haystack)):
if haystack[i:i+m] == needle: return iwhile j and ch != needle[j]:
j = lps[j - 1]Naive rescanning is O(n·m) and re-reads characters already known to match. The LPS array says how much of the current match survives, so the text is scanned exactly once.
Falling back to lps[j] instead of lps[j - 1]
j = lps[j]
j = lps[j - 1]
j is the count of matched characters, so the last matched index is j - 1. Using j reads the entry for a character that hasn't matched yet and the fallback lands in the wrong place.
Building the LPS with an if/else instead of a while loop
if needle[i] == needle[k]: k += 1 else: k = 0
while k and needle[i] != needle[k]:
k = lps[k - 1]
if needle[i] == needle[k]: k += 1Resetting straight to 0 discards partial prefixes that are still viable — on "aabaaac" the correct fallback chain needs several steps. The fallback must repeat until it matches or reaches zero.
Edge cases
LPS = [0,1,2,0] — fallbacks skip re-matching the run of a's.
Return 0 by convention.