Skip to main content
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

String Matching Visualizer

Knuth-Morris-Pratt

Step 0 / 0
Speed 100ms
Step Progress 0 / 0
Comparisons 0
Matches Found 0
Status Ready
Text / Pattern
Comparing
Matched
Window / Aux highlight
Match found
Step Explanation

Select an algorithm and press Play to watch the pattern slide across the text.

—
Pseudocode 
 
 
 
 
  
 
 
Knuth-Morris-Pratt (KMP)
  
 
  Intermediate (3/5)
 
~60 minutes   LPS prefix table  Linear-time matching  Never-backtracking text pointer  Pattern shifting on mismatch  
Prereqs: String basics, Prefix/suffix reasoning  
 
Quick Reference
Knuth-Morris-Pratt
KMP finds all occurrences of a pattern in a text in linear time by precomputing an LPS (longest proper prefix-suffix) table. When a mismatch occurs, the pattern shifts by a known safe amount instead of restarting the comparison.

Difficulty: Intermediate (3/5)
string
Complexity
Best Time
O(n)
Average Time
O(n)
Worst Time
O(n + m)
Space
O(m)
When to Use
Use KMP when you need all occurrences of a fixed pattern in a large text and want guaranteed linear worst-case behavior — no backtracking on the text pointer.
Pros
  • Linear worst case O(n + m)
  • The text pointer never moves backward
  • LPS table makes the "shift" logic explicit
Cons
  • More complex than naive scanning
  • Building LPS is a subtle step to get right
  • O(m) extra space for the table
History
The Knuth-Morris-Pratt algorithm was developed in 1974 and published in 1977 by Donald Knuth and Vaughan Pratt, working with James Morris. It was one of the first linear-time string-matching algorithms and introduced the prefix-function technique.
 
 
Searching for a pattern in a text is easy — naive scanning compares every window, but that’s O(n·m) and repeats work. KMP finds all occurrences in linear time by remembering how much of the pattern already matched. When a mismatch happens, it never re-examines matched text; a precomputed table says exactly how far to shift the pattern instead of restarting from scratch.


How It Works


    

  1. Build LPS — for each prefix of the pattern, store the length of its longest proper prefix that is also a suffix. This is the “memory” of the algorithm.
    2. 

  2. Match phase — scan the text with a pointer that never moves backward.
    3. 

  3. On mismatch — instead of resetting, jump j = LPS[j-1]; the already-matched prefix tells you how much can be reused.
    4. 

  4. On full match — record the position, then set j = LPS[j-1] and keep scanning for more occurrences.
    5. 



Key Insight


The LPS table answers: “I matched up to pattern position j and the text char differs — how much of my current match is still usable?” Because it’s the longest proper prefix that is also a suffix, the shifted pattern still aligns with everything already scanned. The text pointer only moves forward, and j only decreases through LPS jumps — together that bounds the total work at O(n + m).


Worked Example


The visualizer matches pattern P = ABABCABAB in text T = ABABDABACDABABCABAB.


The LPS table for the pattern: [0, 0, 1, 2, 0, 1, 2, 3, 4].


Watch the mismatch at the C vs D clash:


  T: A B A B D A B A C D A B A B C A B A B
  P: A B A B C A B A B
           ↑ j = 4, T = D, P = C → mismatch


LPS[3] = 2, so the pattern shifts by 2 and comparison resumes from P[2] — the text pointer never goes back. Scanning continues to position 10, where the full match ABABCABAB is reported. Total work stays linear even though the pattern appears only once.


Edge Cases & Pitfalls


    

  • Overlapping occurrences: after a match, set j = LPS[m-1] — otherwise overlapping hits are missed.
    • 

  • No prefix-suffix overlap: LPS = 0 means the pattern fully shifts; the text pointer still doesn’t move back.
    • 

  • Pattern longer than text: trivially no matches; guard against indexing errors.
    • 

  • LPS off-by-one: it’s the proper prefix-suffix — a full-length prefix would defeat the shift.
    • 

  • Empty pattern: by convention matches everywhere or nowhere; define behavior explicitly.
    • 



Comparison: KMP vs Other Matchers





































AspectNaiveKMPRabin-Karp
Worst timeO(n·m)O(n + m)O(n·m)
Text pointerResetsNeverRolls hash
Extra spaceO(1)O(m)O(1)
Multi-patternAwkwardAwkwardNatural


Applications


    

  • Text editors — grep and editor search use linear matchers
    • 

  • Pattern in DNA/protein sequences — long exact patterns
    • 

  • Parsers — lexical analysis locating tokens efficiently
    • 



Practice Trajectory


    

  1. Build the LPS table for ABABCABAB by hand and confirm [0,0,1,2,0,1,2,3,4].
    2. 

  2. Trace the visualizer’s mismatch at the D and verify the shift of 2.
    3. 

  3. Explain why the text pointer never needs to move backward.
    4. 

  4. Confirm the single match at position 10 by hand.
    5. 

  5. Extend the scan to find overlapping occurrences and note the j = LPS[m-1] rule.
    6.