Intuition First: Finding a Phrase in a Book#

Say you're skimming a book for the exact phrase "once upon a time". Your eyes slide along each line, and the moment the first word matches, you check whether the next words match too. If they don't, you shrug and keep sliding from where you were. That is substring search: line the pattern (the needle) up at each position in the text (the haystack) and check for a full match.

The clever upgrade, which the KMP algorithm adds further down, is remembering what you have already matched, so a mismatch never forces you to re-read letters you have already seen. It's the difference between re-reading a sentence from scratch every time you trip on a word, versus picking up right where you stumbled.

The Problem#

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

This is the classic str.find() or string.indexOf() problem.

text
text

Approach 1: Brute Force Sliding Window, O(N * M)#

We align needle at each possible starting index of haystack and check character by character.

  • Time Complexity: $O((N - M + 1) \times M)$ which simplifies to $O(N \times M)$ in the worst case (e.g. haystack = "aaaaaaaaab", needle = "aaab").
  • Space Complexity: $O(1)$ auxiliary space.

Approach 2: Knuth-Morris-Pratt (KMP) Algorithm, O(N + M)#

KMP avoids resetting the search pointer all the way back when a mismatch occurs. It uses a LPS (Longest Proper Prefix which is also a Suffix) table to know how many characters we can safely skip.

  • Time Complexity: $O(N + M)$ because the pointers never move backward.
  • Space Complexity: $O(M)$ to store the LPS array.

KMP Substring Search in Action#

Let's take the example in the visualization below: haystack = "CDAABAABAAB" and needle = "AABAA". The strip along the top holds the pattern and its LPS table, [0, 1, 0, 1, 2]. Read that last entry as "the final two characters AA of the pattern are also its first two".

That single number is the whole optimization. Play it through and watch the moment after the first match at index 2:

  • The pattern matches haystack[2..6] completely. Brute force would now shove the pattern back to index 3 and re-read characters it has already seen.
  • KMP instead sets j = lps[4] = 2, which slides the pattern to index 5 while keeping the two As it already matched. The text pointer i never moves backwards; it just carries on at index 7.
  • Comparison resumes mid-pattern and rolls straight into a second match at index 5.

Two matches, and every character of the haystack was read exactly once. (The visualization keeps scanning past the first hit so you can see the skip. The indexOf version in the code above would simply return 2 and stop.)

Key Insight#

The brute-force approach does redundant checks, while KMP remembers previous character comparisons to skip ahead. While KMP is harder to implement from memory, its $O(N + M)$ running time pays off in heavy text-processing pipelines.