How does the KMP string-matching algorithm work? | Interview Question

Q: How does the KMP string-matching algorithm work?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First You are reading a long necklace of beads, looking for the colour pattern red-blue-red-blue-green. You have matched red, blue, red, blue... and the next bead is red, not green. The naive reaction is to slide your finger back to the second bead you looked at and start all over again. But wait: the last two beads you just matched were red, blue, which is exactly how the pattern **starts**. You do not need to look at them again. You can keep your finger where it is and pretend you have already matched "re

The problem

Question presented to candidate: "Explain how the Knuth-Morris-Pratt algorithm finds a pattern in a text, then implement it in Python: build the failure table and return every index where the pattern starts. Why is it linear?"

What a strong answer should cover:

The naive search restarts the pattern after a mismatch and is O(n * m) on repetitive input.
The LPS (failure) array: lps[i] is the longest proper prefix of p[0..i] that is also a suffix; built in O(m) with the k = lps[k - 1] fallback.
The search keeps the text index moving forward only; on a mismatch j = lps[j - 1]; after a full match j = lps[m - 1] to catch overlaps.
O(n + m) time by amortised analysis (j rises at most n times, so it falls at most n times); O(m) space.
Python specifics: in production use str.find / in (much faster than a pure-Python loop); find returns -1 while index raises ValueError; strings are immutable sequences of code points, so t[i] is one character.

Code / implementation expected: Yes — build_lps(p) and kmp_search(t, p) in Python, returning all match positions.

dsa
strings
pattern-matching

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

You are reading a long necklace of beads, looking for the colour pattern red-blue-red-blue-green. You have matched red, blue, red, blue... and the next bead is red, not green. The naive reaction is to slide your finger back to the second bead you looked at and start all over again. But wait: the last two beads you just matched were red, blue, which is exactly how the pattern starts. You do not need

The solution is hidden so you can try first

12 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBuild the LPS table and find every match, overlaps included

Practice

PythonNaive search vs KMP, counting character comparisons

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.