DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Z Function

#algorithms #coding #computerscience #tutorial

Intuition

The Z Algorithm is used to find all occurrences of a pattern in a text in linear time.

The main idea is to avoid comparing the same characters repeatedly.

Instead of checking every position from scratch, the algorithm remembers a range called the Z-Box.

Z-Box = [L, R]
Enter fullscreen mode Exit fullscreen mode

This is the segment where we already know the substring matches the prefix of the string.

For every new index:

  • If it lies outside the Z-Box, compare characters normally.
  • If it lies inside the Z-Box, reuse previously computed values instead of comparing again.

This avoids redundant comparisons and makes the algorithm run in O(N) time.

Brute Force Approach

For every index i,

compare the substring starting at i with the prefix of the string character by character.

Example

String

aabcaabxaaaz

Index = 4

Compare

aabxaaaz

with

aabcaabxaaaz
Enter fullscreen mode Exit fullscreen mode

Keep matching until characters differ.

Repeat this process for every index.

Complexity

  • Time: O(NĀ²)
  • Space: O(1)

Optimal Approach (Z Algorithm)

Observation

Many comparisons are repeated.

Instead of recomputing them,

maintain a Z-Box.

[L, R]
Enter fullscreen mode Exit fullscreen mode

where

s[L...R]

=

s[0...R-L]
Enter fullscreen mode Exit fullscreen mode

For every index:

Case 1: Outside Z-Box 

i > R
Enter fullscreen mode Exit fullscreen mode

Start matching from scratch.

Expand the Z-Box as far as possible.

Case 2: Inside Z-Box 

i <= R
Enter fullscreen mode Exit fullscreen mode

Reuse the previously computed value.

Mirror index

k = i - L
Enter fullscreen mode Exit fullscreen mode

If

Z[k] < R-i+1
Enter fullscreen mode Exit fullscreen mode

then simply copy

Z[i] = Z[k]
Enter fullscreen mode Exit fullscreen mode

Otherwise,

continue matching beyond R and update the Z-Box.

Pattern Matching

To search a pattern,

create a new string:

Pattern + "$" + Text
Enter fullscreen mode Exit fullscreen mode

Example

Pattern

abc

Text

xyzabcabc

Combined

abc$xyzabcabc
Enter fullscreen mode Exit fullscreen mode

Compute the Z-array.

Whenever

Z[i] == Pattern Length
Enter fullscreen mode Exit fullscreen mode

the pattern is found.

Java Code 

public static int[] zFunction(String s) {

    int n = s.length();
    int[] z = new int[n];

    int l = 0, r = 0;

    for (int i = 1; i < n; i++) {

        if (i <= r) {
            z[i] = Math.min(r - i + 1, z[i - l]);
        }

        while (i + z[i] < n &&
               s.charAt(z[i]) == s.charAt(i + z[i])) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}
Enter fullscreen mode Exit fullscreen mode

Complexity

  • Time: O(N)
  • Space: O(N)

Interview One-Liner: The Z Algorithm computes the longest prefix match starting from every index using a Z-Box (L, R) to reuse previous computations, enabling linear-time pattern matching.

Top comments (0)