Z Function

Algorithm

Why do we use Z-Function Algorithm?

When we want to find all occurrences of a pattern in a large text, the Z-function provides a fast and elegant way to do it in linear time. Unlike Rabin-Karp which uses hashing, the Z-algorithm relies on prefix matching using a sliding window.

The idea is to construct a new string by concatenating the pattern, a special separator (like $), and the text. We then compute the Z-array, which tells us for each position in this string, how many characters match the prefix of the entire string. A full match (Z-value equal to pattern length) tells us that the pattern occurs in the text at that position.

This method is fast because it reuses previous comparisons using a window-based approach, and avoids unnecessary checks.

Construct a new string by joining the pattern, a special character (e.g., $), and the text.
Compute the Z-array for this combined string.
The Z-array stores, at each index, the length of the longest prefix match starting from that index.
For every position in the Z-array where the value is equal to the length of the pattern, it means the pattern occurs in the text at that position.
Collect and return all such indices as positions where the pattern occurs in the text.