KMP Algorithm / LPS Array
Return the first index of needle in haystack — in O(n+m) via KMP.
Intuition
When a mismatch happens after matching k chars, naive search restarts from scratch — but we already know those k chars. The LPS array (longest proper prefix that is also a suffix) says how much of the match survives: fall back to lps[k−1] and keep going. The text pointer never moves backward.
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
Build LPS on the needle
lps[i] = length of the longest proper prefix of needle[0..i] that is also its suffix. Built in O(m) with the same fallback logic KMP uses.
Scan with fallback
Match text and pattern pointers; on mismatch with j > 0, set j = lps[j−1] (don't touch i). On j == 0, advance i.
Why linear
i only advances, and j falls back at most as much as it advanced → ≤ 2n pointer moves.
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.