Z-Algorithm
The Z-Algorithm finds all occurrences of a pattern in a text in linear time O(N + M) by constructing a Z-array.
Z-Algorithm
Ready
Controls
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
The Core Idea: Like KMP, Z-Algorithm uses past information to avoid redundant comparisons.
It constructs a Z-array where Z[i] is the length of the longest substring starting from i that is also a prefix of the string.
For pattern matching, we create a new string P + '' + T. Any index i where Z[i] equals the pattern length indicates a match.
Concept
The 'Z-Box': We maintain a range [L, R] which is the rightmost segment found so far that matches a prefix of the string.
- Case 1 (i > R): Compute Z[i] naively. Update L and R if a match is found.
- Case 2 (i <= R): Use previously computed values inside the Z-box. If the value stays within the box, copy it. If it touches the boundary R, extend the search naively.
How it Works
- Concat: Create string
S = Pattern + '' + Text. - Build Z-Array: Iterate through
Smaintaining the[L, R]window. - Identify Matches: Loop through the Z-array part corresponding to the Text. If
Z[i] == len(Pattern), a match starts at that position.
Step-by-Step Breakdown
1. Initialize `L = 0`, `R = 0`, build `Z` array of size `N`.
2. Loop `i` from 1 to `N-1`.
3. If `i > R`: Reset `L, R` to `i`, match prefix with substring starting at `i`. Update `Z[i]` and `R`.
4. If `i <= R`: Let `k = i - L`.
- If `Z[k] < R - i + 1`: `Z[i] = Z[k]` (use precomputed).
- Else: `L = i`, match from `R+1` onwards, update `Z[i]` and `R`.
When to Use
- Exact pattern matching in linear time.
- Finding the longest prefix of a string that is also a suffix (similar to KMP).
- String perioidiicity analysis.
When NOT to Use
- Multiple pattern matching (use Aho-Corasick or Trie).
- Wildcard matching (use FFT-based approach).
How to Identify
"Find all occurrences of P in T", "Longest common prefix of suffixes", "Linear time string matching".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.