KMP Pattern Matching — O(n+m) String Search Every FAANG Interview Tests [LC 28]

Problem Statement#

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Constraints:

• 1 <= haystack.length, needle.length <= 10^4
• haystack and needle consist of only lowercase English letters

Example 1:

Input:  haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and index 6. The first occurrence is at index 0.

Example 2:

Input:  haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" does not occur in "leetcode".

Example 3:

Input:  haystack = "aabaabaaf", needle = "aabaaf"
Output: 3
Explanation: "aabaaf" starts at index 3.

Why This Problem Matters#

LC 28 is the entry point to the entire family of pattern-matching algorithms. The naive O(n*m) approach works for small inputs but fails at scale — imagine searching a genome database of 3 billion characters for a 100-character gene sequence. That is where KMP earns its place.

Google, Amazon, and Meta ask this question because it tests whether you understand that information gathered during failed comparisons is not lost. The insight — "when a mismatch occurs, how far back do we really need to go?" — is a microcosm of the broader algorithmic skill of avoiding redundant work. Every engineer who has debugged a search-and-replace tool, built a text editor, or implemented a protocol parser has encountered this problem in disguise.

Beyond the direct application, the failure function (LPS array) technique reappears in Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214), and the string rotation check. Mastering KMP unlocks a whole class of problems that otherwise seem unrelated.

The Core Insight#

The naive search fails because when a mismatch occurs at position j in the pattern, it resets j to 0 and advances i by only 1 in the text. This throws away the fact that the first j characters of the pattern were matched — they carry structural information about the pattern itself.

KMP exploits this with the Longest Prefix Suffix (LPS) array, also called the failure function. lps[i] = the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. "Proper" means the prefix is not the whole string.

When a mismatch occurs at pattern[j], instead of resetting to 0, we jump to pattern[lps[j-1]]. Why? Because we know pattern[0..lps[j-1]-1] matches the text just before the mismatch point. We reuse that partial match instead of discarding it.

Building the LPS array works by maintaining a length pointer that tracks the length of the current prefix-suffix. When characters match, length grows. When they mismatch and length > 0, we fall back to lps[length-1] — not to 0. This fallback is itself KMP applied to the pattern.

Visual Dry Run#

Pattern: "aabaaf", Text: "aabaabaaf"

Step 1 — Build LPS:

pattern:  a  a  b  a  a  f
index:    0  1  2  3  4  5
lps:      0  1  0  1  2  0
 
- i=1: pattern[1]='a' == pattern[0]='a'  → lps[1]=1, length=1
- i=2: pattern[2]='b' != pattern[1]='a'  → length = lps[0] = 0
        pattern[2]='b' != pattern[0]='a' → lps[2]=0
- i=3: pattern[3]='a' == pattern[0]='a'  → lps[3]=1, length=1
- i=4: pattern[4]='a' == pattern[1]='a'  → lps[4]=2, length=2
- i=5: pattern[5]='f' != pattern[2]='b'  → length = lps[1] = 1
        pattern[5]='f' != pattern[1]='a' → length = lps[0] = 0
        pattern[5]='f' != pattern[0]='a' → lps[5]=0

Step 2 — Search:

text:    a  a  b  a  a  b  a  a  f
index:   0  1  2  3  4  5  6  7  8
         ↑                          i=0, j=0 → match, i=1,j=1
            ↑                       i=1, j=1 → match, i=2,j=2
               ↑                    i=2, j=2 → match, i=3,j=3
                  ↑                 i=3, j=3 → match, i=4,j=4
                     ↑              i=4, j=4 → match, i=5,j=5
                        ↑           i=5, j=5='f' vs text[5]='b' → MISMATCH
                                    j = lps[4] = 2 (don't reset to 0!)
                        ↑           i=5, j=2='b' vs text[5]='b' → match, i=6,j=3
                           ↑        i=6, j=3='a' vs text[6]='a' → match, i=7,j=4
                              ↑     i=7, j=4='a' vs text[7]='a' → match, i=8,j=5
                                 ↑  i=8, j=5='f' vs text[8]='f' → match, i=9,j=6
                                    j == pattern.length → FOUND at index i-j = 9-6 = 3

Answer: 3. The critical moment is at the mismatch: instead of restarting from text[1], we jump j from 5 to 2 and continue from text[5]. The prefix "aab" was reused.

Common Mistakes#

1. Resetting j to 0 on every mismatch. This is the naive approach, not KMP. The whole point is j = lps[j-1], not j = 0. Many candidates write KMP's structure but put j = 0 and lose all the efficiency.

2. Off-by-one in the elif i < len(text) guard. During search, the condition for advancing i when j == 0 and there is a mismatch should increment i. Forgetting this check creates an infinite loop.

3. Not handling the sentinel character in combined strings. When using KMP for problems like Shortest Palindrome, you concatenate s + '#' + rev. Forgetting '#' means the LPS at the last position bleeds across the boundary and gives wrong answers.

4. Building LPS starting from index 0 instead of 1. lps[0] is always 0 by definition (no proper prefix of a single character). Starting the build loop at i = 0 instead of i = 1 causes index errors or incorrect values.

5. Returning only the first match when the problem asks for all matches. After finding a match at position i - j, set j = lps[j-1] and continue — do not reset to 0 and do not stop.

6. Forgetting that lps is built on the pattern, not the text. Students sometimes build the LPS array on the text, which produces garbage. The LPS encodes structural information about the pattern's self-similarity.

7. Confusing the return value. The match starts at i - j where i is the text pointer and j is the pattern length at the moment of the full match. Using i - len(pattern) + 1 or similar variations causes off-by-one errors.

Solutions#

Python#

def strStr(haystack: str, needle: str) -> int:
    # Edge case: empty needle matches at index 0
    n, m = len(haystack), len(needle)
    if m == 0:
        return 0
 
    # --- Phase 1: Build the LPS (failure function) array for needle ---
    lps = [0] * m          # lps[i] = length of longest proper prefix-suffix of needle[0..i]
    length = 0             # length of current matching prefix
    i = 1                  # start from index 1; lps[0] is always 0
 
    while i < m:
        if needle[i] == needle[length]:
            # Characters match: extend the prefix-suffix
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            # Mismatch but we have a fallback: jump to lps[length-1]
            # This avoids resetting to 0 and reuses the earlier partial match
            length = lps[length - 1]
        else:
            # length == 0 and mismatch: lps[i] stays 0
            lps[i] = 0
            i += 1
 
    # --- Phase 2: Search haystack for needle using the LPS array ---
    i = 0  # pointer into haystack
    j = 0  # pointer into needle
 
    while i < n:
        if haystack[i] == needle[j]:
            # Characters match: advance both pointers
            i += 1
            j += 1
 
        if j == m:
            # Full pattern matched: return start index
            return i - j
            # For all occurrences: record i-j then do j = lps[j-1]
 
        elif i < n and haystack[i] != needle[j]:
            if j > 0:
                # Use failure function: don't reset j to 0
                j = lps[j - 1]
            else:
                # j == 0: no prefix to reuse, advance text pointer
                i += 1
 
    return -1  # needle not found

JavaScript#

function strStr(haystack, needle) {
    const n = haystack.length;
    const m = needle.length;
 
    // Empty needle always matches at index 0
    if (m === 0) return 0;
 
    // --- Phase 1: Build LPS array for needle ---
    const lps = new Array(m).fill(0); // lps[i] = longest proper prefix-suffix length
    let length = 0;  // current matching prefix length
    let i = 1;       // index into needle for LPS construction
 
    while (i < m) {
        if (needle[i] === needle[length]) {
            // Match: extend the prefix-suffix, record length, advance
            lps[i] = ++length;
            i++;
        } else if (length > 0) {
            // Mismatch with a fallback: jump via lps, do NOT advance i
            length = lps[length - 1];
        } else {
            // Mismatch at start: lps[i] stays 0, advance i
            lps[i] = 0;
            i++;
        }
    }
 
    // --- Phase 2: Search haystack ---
    i = 0;  // haystack pointer
    let j = 0;  // needle pointer
 
    while (i < n) {
        if (haystack[i] === needle[j]) {
            // Characters match: advance both
            i++;
            j++;
        }
 
        if (j === m) {
            // Full match found: return start position
            return i - j;
        } else if (i < n && haystack[i] !== needle[j]) {
            if (j > 0) {
                // Reuse partial match via failure function
                j = lps[j - 1];
            } else {
                // No partial match to reuse: advance text
                i++;
            }
        }
    }
 
    return -1;  // not found
}

Complexity Analysis#

The naive approach costs O(n * m) in the worst case (e.g., text = "aaaa...a", pattern = "aaa...ab"). KMP reduces this to O(n + m) by never re-examining a character in the text — the text pointer i only moves forward.

Follow-up Questions#

Q: How would you find all occurrences, not just the first? After finding a match at i - j, instead of returning, record the position and set j = lps[j - 1] to continue. This allows overlapping matches. For example, pattern "aa" in text "aaaa" produces [0, 1, 2].

Q: What if the pattern is longer than the text? Return -1 immediately. This is an O(1) short-circuit.

Q: How does KMP compare to the built-in str.find() or indexOf()? Built-in methods in Python and JavaScript use optimized variants (Boyer-Moore-Horspool or similar) that perform better in practice with random text. KMP has the advantage of guaranteed O(n + m) worst-case performance and is preferred when the text is adversarial (e.g., long runs of repeated characters).

Q: Can you solve Repeated Substring Pattern (LC 459) with KMP? Yes. Build the LPS array for s. If lps[-1] > 0 and len(s) % (len(s) - lps[-1]) == 0, then s is composed of repeated substrings. This is a direct application of the failure function.

This Pattern Solves#

• LC 28 — Find the Index of the First Occurrence in a String
• LC 214 — Shortest Palindrome (KMP on s + '#' + reverse(s))
• LC 459 — Repeated Substring Pattern (LPS at last index)
• LC 686 — Repeated String Match (KMP on repeated haystack)
• LC 1392 — Longest Happy Prefix (the LPS array itself is the answer)
• LC 796 — Rotate String (check if s is substring of s + s)
• Any "does string A contain string B as substring" question at scale

Key Takeaways#

• KMP achieves O(n+m) time by ensuring the text pointer i only moves forward — it never backtracks.
• The LPS (failure function) array encodes the self-similarity of the pattern: lps[i] is the longest proper prefix of pattern[0..i] that is also a suffix.
• On a mismatch at position j in the pattern, jump to pattern[lps[j-1]] — reuse the already-matched prefix instead of restarting from 0.
• The LPS array is built in O(m) using the same fallback logic applied to the pattern itself.
• Starting the LPS build loop at index 1 (not 0) is required — lps[0] is always 0 by definition.
• The sentinel character '#' is essential when concatenating pattern + '#' + text for problems like Shortest Palindrome — without it, the LPS bleeds across boundaries.
• The KMP failure function directly enables LC 459 (Repeated Substring Pattern), LC 214 (Shortest Palindrome), and LC 1392 (Longest Happy Prefix) without modification.