KMP Algorithm Visualizer

Explore KMP prefix-table construction and pattern matching with animated fallback jumps, step controls, and comparison metrics.

Current status: Ready. Use the controls to begin exploring KMP.

KMP Algorithm Visualizer

Phase 1: Building LPS Array
A
B
A
B
C
A
B
A
B
0
1
2
3
4
5
6
7
8
0
LPS array (so far)
i = 1len = 0

Build the LPS (failure) array from the pattern.

Step 1 / 44

Animation Legend

Comparing Now
Mismatch / Fallback
Match

Phase 1 builds the LPS array by comparing the pattern against itself, recording the longest prefix that's also a suffix ending at each position. Phase 2 searches the text: on a mismatch, the pattern pointer jumps using the LPS array instead of restarting from scratch, so the text pointer never moves backward.

Java Implementation

public int[] buildLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0, i = 1;
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

public List<Integer> kmpSearch(String text, String pattern) {
    int[] lps = buildLPS(pattern);
    List<Integer> matches = new ArrayList<>();
    int i = 0, j = 0;
    while (i < text.length()) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++; j++;
            if (j == pattern.length()) {
                matches.add(i - j);
                j = lps[j - 1];
            }
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return matches;
}
Time Complexity: O(n + m)

What is the KMP Algorithm?

The Knuth-Morris-Pratt algorithm speeds up string matching by never re-examining a text character it has already matched. It precomputes an LPS ("longest proper prefix that is also a suffix") array from the pattern alone, which tells it exactly how far to shift the pattern after a mismatch instead of restarting from the beginning.

This guarantees linear O(n + m) time in the worst case, unlike the naive approach's O(n · m), and unlike Rabin-Karp, KMP never has to deal with hash collisions since it works directly on characters.

Time & Space Complexity

  • Build LPS ArrayO(m)
  • Search PhaseO(n)
  • SpaceO(m)

* n = text length, m = pattern length. No worst-case blowup, unlike naive search.

Real-World Use Cases

  • ✓
    Text EditorsPowering reliable "find" functionality with guaranteed linear-time search.
  • ✓
    Network Intrusion DetectionScanning packet streams for known attack signatures in real time.
  • ✓
    BioinformaticsFinding exact substring matches within DNA or protein sequences.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

KMP Algorithm Complete Info Card

String MatchingGuaranteed Linear Time

KMP precomputes a failure function (LPS array) from the pattern, letting the search skip re-comparing characters it has already matched instead of backtracking through the text.

Algorithm Characteristics

Build LPS Array

Pattern compared against itself once

O(m)

Search Phase

Text pointer never moves backward

O(n)

Overall Time

Guaranteed linear time, no worst-case blowup

O(n + m)

Space Complexity

The LPS array is the size of the pattern

O(m)

Core Technique

Reuses partial matches instead of restarting

Failure Function

Text Backtracking

The key advantage over naive string search

None

Algorithm Steps

1

Build the LPS array by comparing the pattern to itself

2

Start scanning the text with both pointers at 0

3

On a character match, advance both pointers

4

On a full pattern match, record it and fall back using LPS

5

On a mismatch, jump the pattern pointer via LPS (not the text pointer)

6

If the pattern pointer is already 0, advance the text pointer only

When to Use

  • •Guaranteed worst-case linear time is required
  • •Highly repetitive patterns (e.g. "AAAAB") that punish naive search
  • •Streaming text where re-reading old input isn't possible

When to Avoid

  • •Searching for many patterns at once (Rabin-Karp scales better)
  • •Very large alphabets where Boyer-Moore's skips outperform it
  • •Simple one-off searches where a built-in string method suffices
Did You Know? The LPS array is also called the "failure function" because it tells the algorithm exactly how to recover after a match attempt fails.
LPS arrayLinear timeText editors