The Z-Algorithm for String Matching, Explained

The Z-algorithm finds every occurrence of a pattern inside a text in linear time by building a single array — the Z-array — over a concatenation of the pattern and text, where each entry records how long a match against the start of the string runs from that position. It’s one of a handful of linear-time string-matching techniques, alongside KMP and Rabin-Karp, and it earns its place by being conceptually simpler than either while matching their speed.

What the Z-array stores

For a string S of length n, the Z-array Z has the same length, and Z[i] is defined as the length of the longest substring starting at position i that is also a prefix of S itself. Z[0] is conventionally left undefined (or set to n), since the whole string trivially matches itself.

Take S = "aabxaab". Comparing each suffix against the prefix "aabxaab":

• Z[1] = 1 ("abxaab" shares "a" with the prefix, then b ≠ a)
• Z[2] = 0 ("bxaab" doesn’t even match the first character)
• Z[3] = 0
• Z[4] = 3 ("aab" matches the prefix "aab" exactly, then the string ends)

The key use case comes from concatenating a pattern and text with a separator that appears in neither: S = pattern + "$" + text. Anywhere Z[i] equals the pattern’s length, the text at that position is an exact match for the pattern.

Building it in linear time (the Z-box trick)

A naive approach would recompute each Z[i] from scratch by comparing characters one at a time, which costs O(n) per position and O(n²) overall. The Z-algorithm avoids that by remembering the rightmost match window it has found so far — called the Z-box — bounded by [l, r], the start and end of the furthest-right substring known to match the prefix.

When computing Z[i] for a new position inside an existing Z-box, the algorithm reuses previously computed values: since the substring starting at i is known to appear earlier in the string too (inside the Z-box), its Z-value is already partly known from an earlier position, and only needs to be extended past the boundary r by direct comparison if it might run further. Each character past r is only ever compared once across the whole algorithm, which is what keeps the total work linear — O(n) — despite computing n separate values.

Using it for pattern matching

To search for a pattern P (length m) inside a text T (length n):

1. Build the combined string P + "$" + T, using a separator character that doesn’t appear in either.
2. Compute the Z-array for the combined string, in O(n + m) time.
3. Scan the Z-array (skipping the pattern and separator portion): any index where Z[i] == m marks a match, since it means m characters starting there matched the pattern exactly.

This finds every occurrence of the pattern, not just the first, in a single linear pass — the same guarantee KMP and Rabin-Karp provide, just built via a different mechanism.

Z-algorithm vs KMP vs Rabin-Karp

	Z-algorithm	KMP	Rabin-Karp
Core idea	Prefix-match lengths via a Z-array	Prefix function / failure table	Rolling hash comparison
Time complexity	O(n + m)	O(n + m)	O(n + m) average, O(nm) worst case
Extra space	O(n + m) for the Z-array	O(m) for the failure table	O(1) beyond the hash
Multiple pattern search	Needs re-running per pattern	Needs re-running per pattern	Naturally extends (compare hash sets)
Conceptual complexity	Moderate	Higher (failure function is subtle)	Low (just hashing)

Where it’s used

Beyond textbook string search, the Z-array shows up wherever you need to find repeated structure inside a single string efficiently — detecting the shortest repeating unit of a string, finding all borders (substrings that are both a prefix and a suffix), or as a building block inside more elaborate string-processing pipelines that also lean on structures like suffix arrays for related but more general substring queries. It’s also a frequent stop in algorithm interviews and competitive programming precisely because it’s a compact way to demonstrate linear-time thinking without the notational overhead of KMP’s failure function.

The takeaway

The Z-algorithm turns pattern matching into building one array: Z[i] is how far position i matches the string’s own prefix, computed in linear time by reusing a running match window instead of comparing from scratch at every position. Concatenate pattern and text with a separator, scan for entries equal to the pattern’s length, and you’ve found every match in O(n + m) — the same guarantee as KMP, reached by tracking prefix overlaps instead of failure transitions. Understanding why the technique stays linear is a good exercise in the same reasoning behind Big O analysis more generally.