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

Z-Algorithm

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 
 
 
 
 
  
 
 
Z-Algorithm
  
 
  Intermediate (3/5)
 
~60 minutes   Z-array  Z-box (rightmost matched segment)  Linear-time construction  Separator-joined string  
Prereqs: String basics, Prefix matching, KMP (helpful contrast)  
 
Quick Reference
Z-Algorithm
The Z-algorithm builds a Z-array over "pattern$text": z[i] is the length of the longest substring starting at i that matches a prefix of the string. Every position where z[i] equals the pattern length marks an occurrence.

Difficulty: Intermediate (3/5)
string
Complexity
Best Time
O(n)
Average Time
O(n)
Worst Time
O(n)
Space
O(n)
When to Use
Use the Z-algorithm when you want a compact linear-time pattern matcher that is easy to understand — the Z-array is also useful for other prefix-matching problems.
Pros
  • Truly linear in all cases
  • Simple invariant-based construction
  • Z-array is a reusable primitive
Cons
  • Requires the separator-joined string
  • Less well-known than KMP
  • O(n) extra space for the Z-array
History
The Z-algorithm was popularized by Dan Gusfield in his 1997 textbook "Algorithms on Strings, Trees and Sequences", though the core Z-array idea appeared in earlier linear-time pattern-matching work. It is a favorite for its elegant constant time-per-character argument.
 
 
The Z-algorithm answers a single question for every position: how long is the substring here that matches the string’s own prefix? That one array — the Z-array — turns out to encode enough information to do pattern matching in linear time, with a cleaner invariant than KMP. And unlike many linear-time algorithms, its correctness argument is almost visual.


How It Works


For a string S, the Z-array stores at each position i: z[i] = the length of the longest substring starting at i that matches a prefix of S.


    

  1. Build the joined string for pattern matching: S = pattern + "$" + text. The separator guarantees no match can span the boundary.
    2. 

  2. Maintain the Z-box: track [l, r], the rightmost segment that matches a prefix.
    3. 

  3. Compute each z[i]:

      

    • If i lies inside the box, seed z[i] from z[i − l], capped at r − i + 1.
      • 

    • Then extend while characters agree.
      • 

    

    4. 

  4. Read off matches: every i past the separator with z[i] == m is a pattern occurrence at i − m − 1.
    5. 



Key Insight


When i is inside the current Z-box, the substring at i mirrors the substring at i − l (both start inside the same prefix match), so z[i] can be seeded from already-computed z[i − l] instead of starting from scratch. Extensions only ever advance the right edge r, so across the entire algorithm the total extension work is O(n) — the “each character is touched once” argument, in its cleanest form.


Worked Example


The visualizer matches pattern GEEK against GEEKSFORGEEKS, using the joined string S = GEEK$GEEKSFORGEEKS.


The Z-array:


   S:  G E E K $ G E E K S F O R G E E K S
 z[i]: 0 0 0 0 0 4 3 2 1 0 0 0 0 3 2 1 0 0


    

  • z[5] = 4 (m = 4) → match at text position 5 − 4 − 1 = 0.
    • 

  • z[13] = 3 → prefix match of length 3, but 3 < 4, so no full match there.
    • 



The final report: GEEK occurs at text positions 0 and 8. Watch how z[6], z[7], z[8] are seeded from z[1], z[2], z[3] because they all sit inside the first Z-box [5, 8] — no re-comparison needed.


Edge Cases & Pitfalls


    

  • Separator choice: $ must not appear in pattern or text, or a match could “fake” across the boundary.
    • 

  • Seeding cap: inside the box, z[i] = min(z[i − l], r − i + 1) — the seed is capped by the box’s right edge or it would overclaim.
    • 

  • Positions after the separator: matches are only valid for i > m; don’t read matches from the pattern’s own prefix region.
    • 

  • Empty pattern / empty text: define the Z-array over the empty string explicitly to avoid off-by-one loops.
    • 



Comparison: Z-Algorithm vs KMP
































AspectZ-algorithmKMP
Core arrayz[i] (prefix matches)LPS (prefix-suffix)
InvariantZ-box [l, r]Non-backtracking pointer
Pattern matchingJoin with separatorDirect scan
Ease of proofVery visualMore subtle


Applications


    

  • Linear-time pattern matching — simpler invariant than KMP
    • 

  • Prefix-matching problems — longest repeated substring, compression (LZ77-style)
    • 

  • Text algorithms pedagogy — the Z-box invariant transfers to Manacher’s algorithm
    • 



Practice Trajectory


    

  1. Hand-build the Z-array for GEEK$GEEK... and confirm z[5] = 4.
    2. 

  2. Explain why z[6], z[7], z[8] reuse earlier values instead of re-comparing.
    3. 

  3. Read off both matches (positions 0 and 8) from the Z-array.
    4. 

  4. Change the pattern to GEEKS and recompute — note how the second occurrence becomes exact.
    5. 

  5. Prove the total work is O(n) by tracking how r only moves right.
    6.