Home▸Algorithms & AI▸The Z-Algorithm for String Matching

🧬 The Z-Algorithm for String Matching

Explore how the Z-algorithm builds the Z-array in linear time and uses it to find every occurrence of a pattern inside a text without wasted comparisons.

Algorithms & AI3DModerate60 FPS

The simulator builds the Z-array for a chosen string step by step, visually tracking the current Z-box interval and highlighting exactly which comparisons are skipped through reuse versus which are performed directly, then applies the result to locate every occurrence of a pattern inside a text.

🔬 What It Demonstrates

🎮 How to Use

Enter or select a pattern and a text, then press play to advance through the Z-array construction one position at a time. Watch the L and R pointers mark the current Z-box, observe when a value is copied from an earlier position versus freshly compared, and see matches highlighted in the text once the combined string's Z-array is complete.

💡 Did You Know?

Even though the Z-array of the combined pattern-separator-text string can be almost twice as long as the text alone, the total number of character comparisons performed across the entire construction never exceeds a small constant multiple of that combined length, which is exactly what guarantees linear-time performance no matter how repetitive the input is.

⚙ Under the hood

Explore how the Z-algorithm builds the Z-array in linear time and uses it to find every occurrence of a pattern inside a text without wasted comparisons.

string matchingz-algorithmlinear timepattern searchalgorithmscomputer sciencetext processingz-array

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install