Vibe Engines Learn
ALGORITHMS · 14  /  KMP

The Non- Backtracker.

Search a pattern in a text the naive way and every mismatch throws away everything you learned. KMP never re-reads a character: it studies the pattern's own repeats first, then on a mismatch slides the pattern forward — matching any text in O(n + m).

THE GIST · 20 SECONDS

KMP finds a pattern in a text without backtracking the text pointer. First it builds the LPS table — for each spot in the pattern, the longest prefix that's also a suffix. Then it scans with two pointers: on a match, both advance; on a mismatch, it sets j = lps[j−1] to slide the pattern to its next possible alignment, reusing what already matched. Total work: O(n + m).

  • Patternwhat you're searching for
  • LPSprefix that's also a suffix
  • Mismatchjump, don't restart
  • No rewindtext pointer only moves →

Hit Step to build the failure table, then scan — or Play and watch the pattern slide to the match without ever re-reading the text.

UNDER THE HOOD

What you just played, written down

The whole trick is the failure table. It records how much of the pattern's start is echoed at each point, so a mismatch never forces you back to square one.

How KMP thinks — four moves

  1. Study the pattern first. Build lps[k] = length of the longest proper prefix of the pattern that is also a suffix ending at k.
  2. Scan with two pointers. i over the text, j over the pattern. On a match, advance both.
  3. On a full match, record it. When j reaches the pattern's length, you found an occurrence at i − j. Set j = lps[j−1] to keep looking for overlaps.
  4. On a mismatch, jump — don't restart. If j > 0, set j = lps[j−1]; the text pointer i never moves back. If j = 0, advance i.
WHY THE TEXT POINTER NEVER REWINDS

The already-matched characters are the front of the pattern. The LPS table says how many of them still match after sliding, so KMP resumes mid-pattern instead of re-reading the text — the source of its linear time.

The whole thing in code

def build_lps(p):
    lps = [0] * len(p); length = 0; i = 1
    while i < len(p):
        if p[i] == p[length]:
            length += 1; lps[i] = length; i += 1
        elif length > 0:
            length = lps[length - 1]   # fall back
        else:
            lps[i] = 0; i += 1
    return lps

def kmp(text, pat):
    lps = build_lps(pat); res = []; i = j = 0
    while i < len(text):
        if text[i] == pat[j]:
            i += 1; j += 1
            if j == len(pat):
                res.append(i - j); j = lps[j - 1]
        elif j > 0: j = lps[j - 1]   # jump, no rewind
        else: i += 1
    return res
TIMEO(n + m)build m + scan n
SPACEO(m)the LPS table
THE LPS BUILD IS KMP ON ITSELF

Building the table matches the pattern against itself with the very same two-pointer, fall-back-on-mismatch logic. Learn one loop and you've learned both halves of the algorithm.

⚠ Proper prefix only

"Proper" prefix means not the whole string. Without that, lps[k] would trivially equal k+1 and the fall-back would never make progress. The prefix must be strictly shorter than the substring.

↔ Its cousins

Z-algorithm and the prefix function compute closely related tables. Rabin-Karp uses hashing; Boyer-Moore skips from the end of the pattern and is often faster in practice.

★ Where it's used

grep-style search, DNA/protein search, intrusion detection scanning traffic for signatures, plagiarism checks, and any guaranteed-linear substring search.

SOLVE IT YOURSELF

Solve it: find all matches

This one is yours to write — in Python or TypeScript, running for real in your browser. Build the LPS table and scan the text, returning every start index where the pattern occurs. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement kmp_search(text, pat): return a list of every start index where pat occurs in text (overlaps included). Use the KMP LPS table so the text pointer never moves backward.

HINTS — 4 IDEAS
  1. Build lps: match the pattern against itself; on a mismatch fall back to lps[length-1].
  2. Scan with pointers i (text) and j (pattern). On a match, advance both.
  3. When j == len(pat), record i - j, then set j = lps[j-1] to allow overlaps.
  4. On a mismatch: if j > 0, set j = lps[j-1] (don't touch i); else advance i.
CPython · WebAssembly
QUICK CHECK

Did it stick?

FAQ

KMP, answered

What is the KMP algorithm?

A string-matching algorithm that finds a pattern in a text in O(n + m) by precomputing the pattern's LPS failure table and scanning the text without ever backtracking the text pointer.

What is the LPS table?

For each position in the pattern, the length of the longest proper prefix that is also a suffix ending there. It encodes the pattern's internal repeats so a mismatch can reuse the part that already matched.

Why is it faster than naive search?

Naive search re-compares from scratch on every mismatch — up to O(n·m). KMP never re-reads a text character; it jumps the pattern using the LPS table, for O(n + m) total.

How does it handle a mismatch?

If text[i] != pat[j] and j > 0, set j = lps[j-1] — sliding the pattern to its next viable alignment without moving i. If j == 0, just advance i.

Where is KMP used?

grep-style search, DNA/protein search, intrusion detection, plagiarism checks — anywhere a fixed pattern must be found in a long stream with guaranteed linear time.

RESULT

—

Next → store many patterns at once in a tree of characters and match them together — that's a Trie, and its multi-pattern cousin the Aho-Corasick automaton.

Finished this one? 0 / 17 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →