The Z-Algorithm for String Matching, Explained

Quick Answer

The Z-algorithm builds one array, the Z-array, where each position tells you how long a run of characters starting there matches the very beginning of the string. Once you have that array, finding a pattern inside a text is just gluing pattern + separator + text into one string, building its Z-array, and checking where the value is at least as long as the pattern. The whole thing runs in guaranteed O(n) time.

What the Z-array actually tells you

For a string s of length n, the Z-array is also length n, and z[i] is defined as the length of the longest substring starting at position i that is also a prefix of s itself. In plain terms: stand at position i, start reading forward, and count how many characters in a row match the start of the string before you hit a mismatch (or run out of string).

Take s = "aabxaabxcaabxaabxay". At position 4, the substring starting there is s[4:] = "aabxcaabxaabxay", and the first four characters of that, "aabx", exactly match the first four characters of the whole string, "aabx". The fifth character breaks the match ("c" at that position vs the string's fifth character "a"), so z[4] = 4.

By convention z[0] is usually defined as the full string length n (every string trivially matches itself as a prefix of itself), though some treatments leave it undefined since it's never used by the search logic. This article's implementation sets it to n for completeness.

Two bounding facts are worth knowing early on. First, z[i] can never exceed n - i, there simply aren't more characters left in the string, which doubles as a sanity check when debugging an implementation (a computed value larger than the remaining string length means something is wrong). Second, a maximally repetitive string like "aaaa" produces the Z-array [4, 3, 2, 1], every suffix matches the prefix for as long as it possibly can, since every character is identical. That degenerate case is worth testing against directly, because it exercises the window-extension logic at every single position in a row, exactly the scenario most likely to expose an off-by-one error on a first attempt at this algorithm.

Why this is useful for pattern matching

If you concatenate pattern + separator + text (the separator is any character guaranteed not to appear in either string, which is why '\x00', the null byte, is a common safe choice), then wherever z[i] in the combined string is at least as long as the pattern, you've found an exact occurrence of the pattern in the text starting at that position. That's the entire insight the algorithm is built on: pattern matching becomes a single array-building pass plus a linear scan of that array.

Building the Z-array in linear time, not quadratic

The naive way to build this array is to literally compare characters from scratch at every position, which costs O(n) per position and O(n^2) overall. The Z-algorithm avoids that by reusing information from matches it has already discovered, using two pointers, l and r, that track the boundaries of the rightmost Z-box found so far (a Z-box being a maximal match against the string's prefix).

Here's the key reasoning for position i while scanning left to right:

• If i falls outside the current [l, r) window, there's no shortcut available, so fall back to direct character comparison starting from scratch.
• If i falls inside the window, then the substring starting at i is known to match the substring starting at the corresponding offset inside the prefix, specifically position i - l, because both lie inside a region that's already been proven equal to the string's own prefix. So z[i] can be seeded with min(r - i, z[i - l]), the smaller of "how much of the window is left" and "how far the earlier match at that mirrored position went", before any new comparisons happen.
• After seeding, the algorithm still tries to extend the match further by direct comparison, since the real match might run longer than what the mirrored position alone guarantees.
• If this extension pushes past the current r, the window updates to the new, larger boundaries.

Because every character comparison either extends the rightmost boundary r forward (which can only happen n times total across the whole algorithm) or is skipped entirely via the seeded shortcut, the total work across all positions is bounded by O(n), not O(n^2). This is the same "amortized progress" argument that shows up in KMP's failure-function construction, just applied through a different bookkeeping structure.

Using the Z-array to find a pattern

Once the general-purpose Z-array builder exists, pattern search is almost an afterthought:

1. Build the combined string pattern + separator + text.
2. Compute its Z-array using the builder above.
3. Walk through positions after the separator. Any position where the Z-value is greater than or equal to the pattern length marks a genuine occurrence of the pattern in the text, and the actual starting index in the original text is (position in combined string) - (pattern length) - 1, to account for the pattern and separator prefix sitting in front of the text.

Walking through a concrete case makes the index arithmetic less abstract. Take pattern "abcaby" and text "abxabcabcaby", combined into "abcaby\x00abxabcabcaby". The pattern length is 6, so the separator sits at index 6, and the text itself starts at index 7 of the combined string. The real match happens at index 13 of the combined string, where the Z-value reaches 6 (matching the full pattern length). Subtracting 6 + 1 = 7 gives 13 - 7 = 6, which is exactly the starting index of "abcaby" inside the original text, confirmed directly against the naive search in the code run later in this article.

This design has a nice property worth calling out directly: unlike Rabin-Karp, there's no probabilistic verification step needed here at all, a Z-value meeting the threshold is a guaranteed, exact match, not a candidate to double-check. And unlike KMP, there's no separate failure-function table with its own slightly fiddly construction rules to get right. It's one array, one well-understood meaning for each entry, and one linear scan at the end to collect every match.

It's also worth noticing what this approach does NOT need: no modulus to choose, no base to pick, no probability analysis of collision risk. Every decision Rabin-Karp's design forces on you (is this modulus big enough, is this base safe) simply doesn't exist here, because the Z-array works with exact character equality the whole way through. That's the trade this algorithm makes: slightly more bookkeeping in the array-construction step (the l, r window logic covered next), in exchange for zero probabilistic reasoning anywhere in the pattern-matching step itself.

Python implementation, and a real run against five test cases

Here's the complete implementation, the array builder plus the search wrapper around it:

def z_array(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    z[0] = n
    return z

def z_search(text, pattern, sep="\x00"):
    combined = pattern + sep + text
    z = z_array(combined)
    m = len(pattern)
    positions = []
    for i in range(m + 1, len(combined)):
        if z[i] >= m:
            positions.append(i - m - 1)
    return positions

I ran this against five cases, including overlapping matches and a pattern that doesn't appear at all, checked against a trusted naive search:

text='abxabcabcaby'       pattern='abcaby'   naive=[6] z=[6] [OK]
text='aaaaaaaaaa'         pattern='aaa'      naive=[0, 1, 2, 3, 4, 5, 6, 7] z=[0, 1, 2, 3, 4, 5, 6, 7] [OK]
text='hello world'        pattern='xyz'      naive=[] z=[] [OK]
text='gatcgatcgatc'       pattern='gatc'     naive=[0, 4, 8] z=[0, 4, 8] [OK]
text='mississippi'        pattern='issi'     naive=[1, 4] z=[1, 4] [OK]

All five match the naive search exactly, including the overlapping-match case (eight occurrences of "aaa" inside "aaaaaaaaaa") and a case with repeating structure ("gatc" inside "gatcgatcgatc"), which is exactly the kind of input that trips up implementations that accidentally skip forward by the pattern length instead of checking every position.

The mississippi/"issi" case is worth a second look because its two matches overlap by one character (the match at index 1 covers indices 1 through 4, the match at index 4 covers indices 4 through 7, sharing position 4). An implementation that tried to "consume" matched characters and skip past them, a natural-looking shortcut, would miss the second match entirely. Because the Z-array approach checks the full Z-value fresh at every single position in the combined string, independent of what was found at earlier positions, overlapping matches like this one fall out correctly with zero special-casing.

Seeing the linear-time trick on a real string

To make the l, r window mechanism concrete rather than abstract, here's the actual Z-array computed for a string with deliberately repeating structure, "aabxaabxcaabxaabxay":

aabxaabxcaabxaabxay
[19, 1, 0, 0, 4, 1, 0, 0, 0, 8, 1, 0, 0, 5, 1, 0, 0, 1, 0]

Look at position 9: z[9] = 8. That's the second-longest match in the array, and it's found almost entirely through the window-reuse shortcut, not from-scratch comparison, because the substring starting at position 9 overlaps heavily with structure the algorithm already proved earlier in the scan. Position 13 similarly gets a head start from the window established by position 9's long match. This cascading reuse, each discovery shortening the work needed for the next one, is exactly why the total comparisons across the whole string stay bounded by its length instead of growing with the square of it.

Notice also how most positions have small Z-values (0, 1, or 4), these are genuinely "new" positions with no useful overlap to reuse, so the algorithm correctly falls back to a few direct character comparisons for them. The algorithm isn't claiming everything is reusable, only exploiting the reuse that's actually, provably there.

It's worth putting a number on this rather than leaving the "amortized" claim abstract. For this 19-character string, a naive character-by-character Z-array builder (one that restarts comparison from scratch at every position) would perform up to 19 x 19 = 361 character comparisons in the absolute worst case. The actual window-reusing algorithm performs far fewer, because every comparison that succeeds either extends the shared window r (which can only happen a total of 19 times across the whole run, since r only ever moves forward and is capped at the string length) or is a single failing comparison that stops the current position's extension attempt immediately. That two-part accounting, at most n successful "new ground" comparisons plus exactly one failing comparison per position, is the entire proof that the total work is bounded by roughly 2n, linear, not quadratic.

Z-algorithm vs KMP vs Rabin-Karp

All three guarantee or average out to linear-time single-pattern search, so the real differences are in implementation shape and what each one generalises to:

A genuinely useful distinction for interviews: KMP's failure function is built purely from the pattern, which means KMP can start matching against a text stream before it's even finished arriving (classic use case: searching live network traffic). The Z-algorithm, as commonly implemented, needs the full combined string up front, so it's less naturally suited to streaming, but many people find its single definition ("how far does this match the prefix") easier to reason about correctly than KMP's failure function, which has more edge cases around partial matches.

In practice, the choice between these three often comes down to what you're optimizing for in the moment, not raw performance, since all three hit linear time for the core single-pattern case. If you're in an interview and asked to implement string matching from memory, the Z-algorithm is frequently the easiest to get bug-free on the first try, because its correctness argument (seed from the mirrored position, then extend) is more self-contained than KMP's failure function, which has a well-known tricky edge case around repeated prefixes. If you're building a production text-search feature from scratch rather than reaching for a battle-tested substring search already in your language's standard library, Rabin-Karp's hashing approach is usually the more natural starting point specifically because it extends so easily to searching for many patterns at once. Priodemy's companion article on Rabin-Karp covers that multi-pattern case, and the use cases where trading a worse worst case for simpler generalization is the right trade to make, in more depth.

Common pitfalls and where this actually gets used

Three mistakes show up repeatedly in Z-algorithm implementations:

• Picking a separator that can appear in the text or pattern. If you use a printable separator character and the text happens to contain it too, matches can silently merge across the boundary and produce wrong results. The null byte is a safe default for normal text because it essentially never appears in real strings, but for binary data you need to pick something you can actually guarantee is absent, or use an out-of-band length-prefixed encoding instead.
• Forgetting to offset the index. Positions found in the Z-array of the combined string are offset by len(pattern) + 1 from positions in the original text. Forgetting this subtraction is the single most common off-by-some-constant bug people hit when wiring this algorithm up for the first time.
• Confusing the Z-array with the KMP failure function. They solve overlapping problems and even share some underlying theory, but they are not the same array and don't have the same values for the same string. Treating them as interchangeable in an interview answer is a quick way to lose credibility.

Beyond pattern search itself, the Z-array is a genuinely useful building block for a cluster of related string problems: finding the shortest period of a repeating string, counting distinct borders of a string, and building more advanced structures like suffix automata. If you only remember one thing, remember that the Z-array answers one specific question ("how far does this position match the prefix") and a surprising number of string problems turn out to be that question in disguise.

One more pitfall worth a brief mention: building the Z-array for a string containing characters outside the basic ASCII range needs care in languages where string indexing isn't guaranteed to walk one character at a time (JavaScript's UTF-16 surrogate pairs for certain Unicode characters are the classic trap here). Python's strings index by code point directly, which is part of why the implementation in this article behaves correctly without extra handling, but porting this code to a language with UTF-16 or byte-oriented string indexing needs an explicit decode step first.

Frequently Asked Questions