LeetCode #28 Medium

KMP Algorithm / LPS Array

Return the first index of needle in haystack — in O(n+m) via KMP.

stringkmppattern-matching

02

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.

03

Approach

1

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.

2

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.

3

Why linear

i only advances, and j falls back at most as much as it advanced → ≤ 2n pointer moves.

04

Solution & live demo

python

▶1class Solution:
▶2    def strStr(self, haystack, needle):
▶3        if not needle: return 0
▶4        lps = [0] * len(needle)
▶5        k = 0
▶6        for i in range(1, len(needle)):          # build LPS
▶7            while k and needle[i] != needle[k]:
▶8                k = lps[k - 1]
▶9            if needle[i] == needle[k]:
▶10                k += 1
▶11            lps[i] = k
▶12        j = 0
▶13        for i, ch in enumerate(haystack):        # scan
▶14            while j and ch != needle[j]:
▶15                j = lps[j - 1]
▶16            if ch == needle[j]:
▶17                j += 1
▶18            if j == len(needle):
▶19                return i - j + 1
▶20        return -1

05

Edge cases

Needle with repeats, e.g. "aaab"

LPS = [0,1,2,0] — fallbacks skip re-matching the run of a's.

Empty needle

Return 0 by convention.

06

Complexity

Time

O(n + m)

Space

O(m)

Text pointer never backtracks.