Z Function

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]

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

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]

where

s[L...R]



=



s[0...R-L]

For every index:

Case 1: Outside Z-Box

i > R

Start matching from scratch.

Expand the Z-Box as far as possible.

Case 2: Inside Z-Box

i <= R

Reuse the previously computed value.

Mirror index

k = i - L

If

Z[k] < R-i+1

then simply copy

Z[i] = Z[k]

Otherwise,

continue matching beyond R and update the Z-Box.

Pattern Matching

To search a pattern,

create a new string:

Pattern + "$" + Text

Example

Pattern



abc



Text



xyzabcabc



Combined



abc$xyzabcabc

Compute the Z-array.

Whenever

Z[i] == Pattern Length

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;

}

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.