Faangprep Logo
Log inStart free
Browse curriculum

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[i] is how much of a string's own beginning starts again at position i. Glue the pattern to the front of the text with a separator that appears in neither, compute the Z-array once, and every position whose value reaches the pattern's length is a match. The box is what makes that one pass: the rightmost run that matched the beginning, reused instead of re-compared. Switch to NAIVE to see what finding each position from scratch costs.

SETUP

i

0

1

2

3

4

5

6

7

8

9

10

S

a
b
a
$
a
b
a
b
a
b
a

box

Z

Box

none

Found

0

Compares

0

With box

13

 

Looking for "aba" in "abababa". Z[i] is one number per position — how much of the string's own beginning starts again at i — so glue the pattern to the front of the text with a separator that appears in neither, and every position whose Z value reaches 3 is a place the pattern starts. 10 positions to fill, and no box yet: nothing has matched anything.

Next

k=1, and there is no box to help — nothing has matched far enough to leave one. Compare outward from 1 against the beginning of the string.

Text

Pattern

Method

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

  1. Concat: Create string S = Pattern + '$' + Text.
  2. Build Z-Array: Iterate through S maintaining the [L, R] window.
  3. 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".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Compare its cost with every other algorithm in the Big O cheat sheet.

Previous

Tries

Next

Suffix Array

Frequently Asked Questions

What does Z[i] mean?

The length of the longest substring starting at position i that is also a prefix of the whole string. When the Z-array is built over the pattern, a separator and the text, every position where Z equals the pattern length is an occurrence.

Why is it linear when the inner loop can extend many characters?

Because the right edge of the matched box never decreases. Every character the naive extension compares pushes that edge forward, so those comparisons total at most N over the entire run.

Z-algorithm or KMP?

Both are O(N + M) and either works for exact matching. The Z-array is often easier to reason about and reuse for prefix and periodicity questions, while KMP streams the text without building a combined string.