vizlearn

Implement substring search (strStr)

Interview QuestionsBy Updated

The naive scan re-reads text after every mismatch, which is O(n·m) and genuinely quadratic on repetitive input. KMP precomputes how far the pattern can safely slide, so the text index never moves backwards and the whole search is O(n + m).

Overview

What naive search wastes

Align the pattern at position 0, compare until a mismatch, then restart at position 1. The waste is that the comparisons already made are thrown away: on "aaaaaab" against "aaab", almost every alignment re-reads the same characters.

Worst case O(n·m). Average case on natural text is close to O(n), which is why naive search is a perfectly reasonable answer to give first — then improve it.

StringsCoding problemHard

Step through it

What to watch

  • The table is built first, from the pattern alone.
  • On a mismatch the pattern slides; i stays put.
  • That single property is the whole complexity difference.

Say this out loud

"Naive is O(n·m) and fine for most inputs. KMP builds a prefix table so on a mismatch the pattern slides instead of the text rewinding - O(n + m), and the text pointer only ever moves forward."

Implement substring search (strStr)

Find the first occurrence of a pattern in a text, without using the built-in.

The prefix table

lps[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix of it. That overlap is exactly the information needed: after a mismatch, the characters already matched end in something that also begins the pattern, so the pattern can slide to that alignment without re-reading anything.

The table is built in O(m) using itself — on a mismatch while building, it falls back to lps[length-1] rather than restarting. That line looks wrong and is the reason the build is linear.

The property to state

i never decreases. Every character of the text is examined a bounded number of times, so the search is O(n) after an O(m) preprocessing pass.

Say what you would actually ship: text.find(pattern), which in CPython is a tuned hybrid of Boyer-Moore and Horspool. The point of implementing KMP is the reasoning, and interviewers know that.

Run it in Python

Both searches with their comparisons counted, on ordinary text and then on the repetitive input designed to make naive matching look bad. The gap is the argument for the table.

strstr.pyPython 3
Output
How the code works
  1. length = lps[length - 1]The line that makes the build linear, and the one that looks wrong. On a mismatch it falls back to the next-best border already computed — the table is built using itself.
  2. elif j: j = lps[j - 1]The search's whole trick. The pattern slides forward while i stays put, because the table proves the skipped alignments cannot match.
  3. i never decreasesState this explicitly in an interview. It is the property that turns O(n·m) into O(n + m), and it is what the table was built to guarantee.
  4. text.find(pattern)What you would actually ship. Implementing KMP demonstrates the reasoning; using the built-in demonstrates judgement, and saying both is the complete answer.
Change one thing
  • Lengthen the repetitive input to 500 a's. The naive count grows quadratically while KMP's stays linear.
  • Build the table for "aaaa" and for "abcd". All overlap and none — the two extremes of what it can say.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. In KMP's search loop, which index never moves backwards?
  2. lps[i] stores:
  3. Naive substring search is genuinely quadratic on:





 Cheat sheet
Implement substring search (strStr)
The naive scan re-reads text after every mismatch, which is O(n·m) and genuinely quadratic on repetitive input. KMP precomputes how far the pattern can safely slide, so the text index never moves backwards and the whole search is O(n + m).
INTERVIEW · vizlearn.in/interview/implement-substring-search.html
More in Interview
InterviewIsomorphic stringsInterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?InterviewWhy is `in` slow on a list but fast on a set?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact