The Z-Algorithm for String Matching

What the Z-Array Actually Measures

For a string S of length n, the Z-array is also of length n, and each entry Z of i is defined relative to the whole string S read from its very first character. Concretely, Z of i is the length of the longest common prefix between S itself and the suffix of S that begins at position i. In plain terms: start comparing S from the beginning against S starting at position i, count how many characters match before the first mismatch, and that count is Z of i. Position 0 is a special case and is typically left undefined or set to n, since comparing S against itself trivially matches completely; the interesting information lives in positions 1 through n minus 1. Consider the string abcabcabx. At position 3 the suffix is abcabx, and comparing it against the full string from the start gives a match of abc before hitting a mismatch, so Z of 3 equals 3. At position 6 the suffix is abx, which matches only ab against the prefix, giving Z of 6 equals 2. At position 1 the suffix bcabcabx shares no characters at all with the prefix starting with a, so Z of 1 equals 0. Reading through every position gives a full profile of how self-similar the string is at each offset, which is exactly the information needed later for pattern matching. It helps to think of the Z-array as answering, for every starting point in the string, the question, how far does this look like the beginning all over again. Strings with strong internal repetition, like aaaaa or abcabcabc, produce Z-arrays with large, structured values, while strings with little internal repetition produce Z-arrays dominated by zeros and small numbers. Understanding this definition precisely is essential, because the entire linear-time construction trick depends on reasoning about overlapping intervals of matched characters rather than recomputing each entry from scratch by brute force comparison.

The Naive Approach and Why It Falls Short

The most direct way to compute the Z-array is to loop over every starting position i from 1 to n minus 1, and for each one, compare characters of S beginning at position 0 against characters of S beginning at position i, counting matches until a mismatch occurs or the string ends. This absolutely works and produces a correct Z-array, but its cost can be quadratic in the worst case. Imagine a string made entirely of the same repeated character, such as aaaaaaaaaa. At position 1, the comparison walks almost to the end of the string before finding a mismatch, since everything matches. At position 2, the same long walk happens again, and again at position 3, and so on for every starting position. The total work becomes proportional to n squared, which is far too slow for long strings such as genome sequences, log files, or large documents where n can be in the millions. The frustrating part is that all of this repeated comparison work is, in a very real sense, wasted, because the comparisons made while computing Z of 1 already reveal a great deal of information about what will happen when computing Z of 2, Z of 3, and beyond. If the string matched the prefix for a long stretch starting at position 1, that stretch itself is a substring of S, and its internal structure has already been captured by earlier Z-values computed for positions within that stretch. The naive algorithm throws this information away and starts every comparison completely from scratch, character by character, from position 0. The key insight that produces a linear-time algorithm is to keep track of the furthest-right region of the string that has already been confirmed to match a prefix, and to reuse the previously computed Z-values that fall inside that region rather than re-deriving them, only falling back to direct character comparison when genuinely new territory is being explored beyond what has already been verified.

The Z-Box: Reusing Work with a Sliding Window

The linear-time trick maintains two pointers, conventionally called L and R, which together define what is called the Z-box: the interval from L to R representing the rightmost stretch of the string currently known to match a prefix of S, discovered while computing some earlier Z-value. As the algorithm scans positions left to right, it keeps L and R updated to always reflect the rightmost matching interval found so far. When computing Z of i, there are two cases. If i lies outside the current Z-box, meaning i is beyond R, there is no shortcut available, so the algorithm falls back to direct character-by-character comparison starting from position 0, exactly like the naive method, and if this produces a nonzero match length, L and R are updated to reflect this new, further-reaching Z-box. The second case is the clever one: if i falls inside the existing Z-box, meaning L is less than or equal to i and i is less than or equal to R, then position i corresponds to some position k inside the prefix, specifically k equals i minus L, because the substring from L to R is already known to equal the prefix of that same length. This means the value Z of k, already computed earlier since k is smaller than i, gives strong information about Z of i without any new comparisons. If Z of k is strictly less than the remaining distance to R, meaning the match at position k ended safely before running into the boundary, then Z of i can simply be copied directly from Z of k, no comparison needed at all. But if Z of k reaches or exceeds that remaining distance, the algorithm cannot be certain the match continues past R, because it has no information about characters beyond the Z-box boundary, so it must extend the comparison starting exactly at position R plus one, checking only the new, previously unseen characters, then updating L and R accordingly. This rule, reuse what the Z-box already proved and verify only the unknown remainder, is what collapses the total work across the whole scan down to linear time: every character is involved in at most a small constant number of comparisons overall, since R only ever moves forward and never backward.

From Z-Array to Pattern Matching

Turning the Z-array into a full pattern-search tool requires one more idea: constructing a combined string. Given a pattern P of length m and a text T of length n, build the string P plus a separator character plus T, where the separator is chosen to be a character guaranteed not to appear anywhere in either P or T, such as a null character or another sentinel symbol reserved for this purpose. Compute the Z-array of this combined string using the linear-time procedure just described. Now examine every position i in the combined string that falls within the text portion, meaning after the pattern and the separator. If Z of i equals exactly m, the length of the pattern, that means the suffix of the combined string starting at position i matches the full prefix of the combined string, which is precisely the pattern P itself, character for character. In other words, position i marks the start of an exact occurrence of the pattern inside the text. Because the separator character cannot appear in either string, it is impossible for a match to spuriously cross from the text back into the pattern region or accidentally include the separator, which keeps the matching completely accurate. Since the Z-array of the combined string of length m plus n plus 1 is built in linear time relative to its own length, and scanning it afterward for entries equal to m is also linear, the entire pattern-search procedure runs in time proportional to m plus n, a dramatic improvement over naive matching's proportional-to-m-times-n worst case. This approach also naturally reports every occurrence, not just the first, since the scan continues through the whole array, and it generalizes gracefully to searching for the same pattern across multiple texts, or to related problems like finding the longest substring shared as both a prefix and elsewhere within a single string, or measuring self-similarity for tasks like detecting periodic repetition.

Z-Algorithm Versus KMP: Two Paths to Linear Time

It is natural to ask how the Z-algorithm relates to the Knuth-Morris-Pratt approach, since both achieve linear-time exact pattern matching and both avoid re-examining characters unnecessarily by exploiting the internal structure of the pattern. The core difference lies in what each algorithm actually computes and how it uses that information during the scan. KMP builds a failure function, sometimes called the prefix function, defined purely over the pattern, where each entry records the length of the longest proper prefix of the pattern that is also a suffix ending at that position; during the search phase, KMP slides a single pointer through the text and uses the failure function to decide how far to fall back within the pattern after a mismatch, without ever moving backward through the text. The Z-algorithm instead computes the Z-array over the combined pattern-separator-text string directly, and matches are read off simply by checking where Z equals the pattern length, with no separate fallback-and-retry logic needed during a search pass, since the Z-array construction already embeds all of that reasoning through the Z-box mechanism. In practice this makes the Z-algorithm's logic somewhat easier for many learners to reason about, since there is a single, uniform array-construction procedure rather than two conceptually separate phases, preprocessing the pattern and then scanning the text with a distinct set of rules. KMP, on the other hand, avoids building an explicit combined string and its failure function is often reused directly for other purposes, such as detecting the shortest repeating unit of a string. Both run in linear time and both are entirely deterministic with no randomization involved, so neither is strictly superior; the choice between them in practice often comes down to implementation preference, whether the failure-function perspective or the prefix-matching perspective feels more natural, and whether other properties of the Z-array, like its usefulness for general prefix-similarity queries beyond simple pattern search, are needed elsewhere in a given application.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Z-Algorithm for String Matching and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.