vault

Z-Algorithm

14 min read

Z-Algorithm

The Z-algorithm computes, for a string S of length n, the Z-array Z[0..n-1] where Z[i] is the length of the longest substring of S starting at position i that is also a prefix of S. It runs in O(n) time and is the workhorse for substring search via the trick pattern + "$" + text: any position i in the concatenated string with Z[i] = m corresponds to an occurrence of pattern (length m) in text. The algorithm is conceptually simpler than Knuth-Morris-Pratt (it doesn’t require a failure-function recurrence), is presented as the canonical example in Gusfield’s 1997 textbook Algorithms on Strings, Trees, and Sequences, and shows up constantly in competitive-programming problem sets.

1. Intuition — “How Much of the Beginning Repeats Here?”

Pick any string and look at every position i ≥ 1. Ask the question: if I started reading the string from position i, how many characters in a row would also match the start of the original string?

Take S = "aabcaabxaaaz" (length 12). Starting at position 4 we see "aabxaaaz". How many characters of that match the prefix of S ("aabcaabxaaaz")? 'a' == 'a', 'a' == 'a', 'b' == 'b' — three matches; the fourth is 'x' vs 'c', so Z[4] = 3.

That’s it — the Z-array just records this number for every starting position. The leftmost entry Z[0] is conventionally either left undefined or set to n (the prefix matches itself entirely); both conventions appear in the literature.

The real-world analogy is the auto-correlation of a sequence: how does the string look like its own shifted copy? Repetitive patterns produce large Z[i] values at the period; one-off characters drop the count back to zero. A telegraph operator listening for the start of a known call sign in a noisy stream is doing exactly this — and the Z-array is what they’d memorize ahead of time about their own call sign so that, mid-listen, they can resume an interrupted match instead of restarting.

2. Tiny Worked Example

Compute the Z-array of S = "aabcaabxaaaz" (length 12) by hand to convince ourselves the answer is

i:    0 1 2 3 4 5 6 7 8 9 10 11
S:    a a b c a a b x a a  a  z
Z:    – 1 0 0 3 1 0 0 2 2  1  0

Going position by position:

  • i = 1: S[1..] = "abcaabxaaaz". Match against prefix "aabcaabxaaaz": a == a (1), b vs a mismatch. Z[1] = 1.
  • i = 2: S[2..] = "bcaabxaaaz". b vs a immediate mismatch. Z[2] = 0.
  • i = 3: c vs a mismatch. Z[3] = 0.
  • i = 4: S[4..] = "aabxaaaz". a a b match (3), then x vs c. Z[4] = 3.
  • i = 5: S[5..] = "abxaaaz". a == a (1), b vs a mismatch. Z[5] = 1.
  • i = 6: b mismatch. Z[6] = 0.
  • i = 7: x mismatch. Z[7] = 0.
  • i = 8: S[8..] = "aaaz". a a match (2), a vs b mismatch. Z[8] = 2.
  • i = 9: S[9..] = "aaz". a a match (2), z vs b mismatch. Z[9] = 2.
  • i = 10: S[10..] = "az". a match (1), z vs a mismatch. Z[10] = 1.
  • i = 11: z mismatch. Z[11] = 0.

The naive computation we just did is O(n²) — for each of n positions we re-scan up to n characters. The Z-algorithm reuses information from previously computed Z values to drop this to O(n). The reuse mechanism is the [l, r] window, explained next.

3. The Algorithm — [l, r] Window of the Rightmost Z-box

We process positions i = 1, 2, …, n − 1 left to right. We maintain two indices l and r (initially l = r = 0) that record the rightmost Z-box seen so far: a half-open interval [l, r) such that S[l..r-1] is equal to the prefix S[0..r-l-1] (a previously discovered match).

When processing position i:

Case A: i ≥ r. No prior info reaches i. Compute Z[i] by naive comparison: extend a counter k while S[k] == S[i + k]. Set Z[i] = k. If i + k > r, update l = i, r = i + k.

Case B: i < r. Position i lies inside the previous Z-box [l, r). The mirror of i inside the prefix is i' = i − l. We already know Z[i']. Two sub-cases:

  • B1: Z[i'] < r − i. The match at the mirror dies before the right boundary r. The same death must occur at i (because everything inside the Z-box agrees with the prefix). So Z[i] = Z[i'] — no comparison needed.

  • B2: Z[i'] >= r − i. The match at the mirror reaches at least to r. Beyond r, we know nothing — r was the right boundary precisely because S[r] != S[r - l]. Set Z[i] = r − i initially, then extend by naive comparison from S[r] vs S[r - i]. Update l = i, r = i + Z[i].

The amortized argument (§5) shows that across all iterations, the right endpoint r only ever increases — every “extend by naive comparison” pushes r strictly forward, and r is bounded by n. So the total comparison work across all iterations is O(n).

3.1 Why the mirror trick works

Inside the Z-box [l, r), the substring S[l..r-1] is equal to the prefix S[0..r-l-1]. So whatever pattern of “matches against the prefix” appears at position i' = i - l inside the prefix also appears at position i inside the Z-box — at least up to where the Z-box ends. Beyond r, the equality breaks (that’s why r is the right boundary). So we can safely copy Z[i'] into Z[i] as long as the match doesn’t try to walk past r; if it does, we have to fall back to character-by-character comparison from r onwards.

This is exactly analogous to KMP’s failure-link reuse, just expressed in terms of a moving “rightmost match window” instead of per-position back-pointers.

4. Pseudocode

ZArray(S):
    n := length(S)
    Z := array of size n, all zeros
    l := 0
    r := 0
    for i in 1 .. n-1:
        if i < r:
            Z[i] := min(r - i, Z[i - l])    # Case B; the min handles B1 vs B2
        # Case A and the "extend" tail of B2 share this loop
        while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
            Z[i] := Z[i] + 1
        if i + Z[i] > r:
            l := i
            r := i + Z[i]
    return Z

5. Python Implementation

def z_function(s: str) -> list[int]:
    """Compute the Z-array of `s` in O(len(s)) time.
 
    Z[0] is set to 0 here by convention (some references set it to len(s)).
    Z[i] for i >= 1 is the length of the longest substring starting at
    position i that matches a prefix of s.
    """
    n = len(s)
    Z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            # Mirror trick: copy from the corresponding position inside the
            # prefix, but never claim more than `r - i` characters because
            # beyond r we have no information.
            Z[i] = min(r - i, Z[i - l])
        # Extend by naive comparison. This loop is the "expensive" part, but
        # the amortized argument (§6) bounds the total work across all i.
        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]
    return Z
 
 
def z_search(text: str, pattern: str) -> list[int]:
    """Find all start indices (0-based) of `pattern` in `text` using the Z-array.
 
    Standard trick: build T = pattern + sep + text where `sep` is a character
    that appears in neither pattern nor text, then any position i with
    Z[i] >= len(pattern) corresponds to a match starting at i - (len(pattern)+1)
    in the original text.
    """
    if not pattern:
        return list(range(len(text) + 1))
    sep = "\x00"
    if sep in pattern or sep in text:
        # Fall back to a guaranteed-fresh sentinel by scanning the alphabet.
        sentinel = max(map(ord, pattern + text)) + 1
        sep = chr(sentinel)
    combined = pattern + sep + text
    Z = z_function(combined)
    m = len(pattern)
    matches = []
    for i in range(m + 1, len(combined)):     # skip the pattern + sep portion
        if Z[i] >= m:
            matches.append(i - m - 1)
    return matches
 
 
# Sanity checks against §2 worked example:
assert z_function("aabcaabxaaaz") == [0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]
assert z_search("ABABDABACDABABCABAB", "ABABCABAB") == [10]

The sentinel character sep matters: it must not appear in either input, otherwise a Z-value can spuriously cross the boundary and over-report a match. The implementation above falls back to picking a fresh code point if the default \x00 is present — a robustness detail that’s easy to forget in interviews.

6. Complexity

  • Time: O(n) for z_function, O(n + m) for z_search (n = text length, m = pattern length).
  • Space: O(n + m) for the Z-array of the concatenated string.

6.1 Amortized argument

The while loop performs character comparisons. We count two kinds:

  1. Successful comparisons (s[Z[i]] == s[i + Z[i]]): each one advances Z[i] by 1 and, when it pushes the right boundary, also advances r by 1 (because the new r = i + Z[i] strictly exceeds the previous r). So the total number of successful comparisons is at most n — bounded by how many times r can grow, and r is at most n.

  2. Failing comparisons (the loop’s exit condition): each iteration of the outer for loop incurs at most one failing comparison. Total: at most n − 1.

Sum: at most 2n character comparisons across the entire algorithm. Each comparison is O(1). Total time: O(n).

This argument is structurally identical to the Knuth-Morris-Pratt amortized proof (§5 of that note) — both algorithms essentially “pay forward” the cost of a match by forbidding subsequent re-examination.

7. Comparison with KMP

AspectZ-AlgorithmKnuth-Morris-Pratt
Preprocessing objectZ-array of pattern + sep + textLPS / failure function of pattern
Substring search timeO(n + m)O(n + m)
Streaming text?No — needs random access to the concatenated stringYes — text pointer is monotone
Conceptual complexitySlightly simpler — no recurrence on the failure values, just one window [l, r]Slightly trickier — the failure-function recurrence needs care
Useful beyond searchCounting Z-box patterns, palindrome decomposition, “string period”DFA construction, Aho-Corasick foundation, period extraction
MemoryO(n + m) (concatenated string)O(m) (just the LPS)

Practical guidance: if you only need substring search of a single pattern, KMP is slightly more memory-efficient and supports streaming. For “all occurrences of pattern in text” plus other prefix-related queries, the Z-array is often the simplest interface. Many competitive programmers carry both as templates.

The two arrays are information-equivalent: Gusfield 1997 §1.4 shows constructive O(n) conversions in both directions. They are different encodings of the same string-self-correlation structure.

8. Variants and Use Cases

The headline application, demonstrated in z_search above. The pattern + sep + text trick is the canonical idiom; without the separator a long match in pattern could blur into the start of text.

8.2 String period detection

The smallest period of S is n − Z[n - p] for the largest p such that i + Z[i] == n for some i = p. Equivalent to the LPS-based period trick from KMP §6.6, just expressed in Z-form.

8.3 Number of distinct substrings

Build the Z-arrays of all n suffixes (each in O(n)), totalling O(n²); use them to count newly seen substrings. The Suffix Array gives O(n log n), but for n ≤ 5000 the Z-based approach is competitive in code clarity.

8.4 Longest palindromic substring (alternative to Manacher’s Algorithm)

For each position i, compute Z-arrays of s and of s + "#" + reverse(s); align to find the longest palindromic radius at every center. Slower than Manacher’s in constants but reuses the Z infrastructure.

8.5 String matching with don’t-care characters

Replace any ”?” with a unique fresh character before applying the Z-algorithm; only matches with Z[i] = m are real matches.

8.6 Suffix Automaton / Suffix Array preprocessing

Z-arrays underpin several O(n)-construction proofs for higher-level string indexes. Conceptually they’re the “first nontrivial linear-time string structure” Gusfield introduces precisely because everything else builds on them.

9. Pitfalls

9.1 Sentinel character collision

If your separator character actually appears in the input, the Z-array will silently over-extend matches across the boundary. Always pick a sentinel guaranteed to be unused — chr(max(input_codepoints) + 1) is the safe choice, or assert the chosen character is absent.

9.2 Z[0] convention

Some references define Z[0] = n, others Z[0] = 0, others leave it undefined. The downstream algorithms care: if you pass the array to a function expecting one convention with the other, you get a one-off bug at position 0. Always check the contract.

9.3 Off-by-one in i < r vs i <= r

The window is half-open [l, r) in this presentation (so r is the first index outside the matched range). Some references use closed intervals [l, r]. The relations Z[i] = min(r - i, Z[i - l]) vs Z[i] = min(r - i + 1, Z[i - l]) differ by one accordingly. Mixing conventions silently corrupts the array.

9.4 Forgetting to update (l, r) on Case A

If the naive computation in Case A finds matches that push past the previous r, you must update (l, r) = (i, i + Z[i]). Otherwise subsequent positions can’t reuse the work and complexity degrades to O(n²) on degenerate inputs (e.g., "aaaa…").

9.5 Treating Z[i] as “longest match ending at i”

A common confusion. Z[i] is the longest match starting at i. The “match ending at i” question is answered by the Z-array of the reverse string.

9.6 Integer overflow on huge strings

For n ≥ 2³¹, Z[i] and i + Z[i] can overflow 32-bit signed integers. Use 64-bit. In Python this is automatic; in C/C++ it isn’t.

10. Diagram — The [l, r] Window Slides Right

flowchart TB
    subgraph "Before processing index i"
        A["[l,r) = previously-discovered Z-box: S[l..r-1] = S[0..r-l-1]"]
    end
    subgraph "At index i, three cases"
        B1["Case A: i >= r — no info; naive scan from S[0] vs S[i]"]
        B2["Case B1: i < r and Z[i-l] < r-i — copy Z[i] := Z[i-l]"]
        B3["Case B2: i < r and Z[i-l] >= r-i — set Z[i] := r-i, then extend by naive scan from S[r-i] vs S[r]"]
    end
    subgraph "After processing"
        C["if i + Z[i] > r: (l,r) := (i, i + Z[i])  — window slides forward"]
    end
    A --> B1 --> C
    A --> B2 --> C
    A --> B3 --> C

What this diagram shows. The three branches the algorithm chooses among at every position. Case A happens when we’ve never matched far enough to cover i yet. Cases B1 and B2 reuse work from the mirror position i' = i - l inside the prefix; B1 is the cheap “just copy” case, B2 is the “copy what we know, then extend past r” case. Only Cases A and B2 ever do new comparison work, and they always push the right boundary r strictly forward — that is the geometric invariant that powers the linear-time bound proven in §6.1.

11. Common Interview Problems

LC# / SourceProblemUse of Z-Algorithm
LC 28Implement strStr()Direct Z-search via pattern + "#" + text
LC 459Repeated Substring PatternZ-array period detection (§8.2)
LC 214Shortest PalindromeZ-array of s + "#" + reverse(s), like the KMP version
LC 3008Find Beautiful Indices in StringTwo Z-arrays for two patterns; merge match positions
LC 5Longest Palindromic SubstringZ-based palindrome radii (alternative to Manacher)
LC 1392Longest Happy PrefixFind largest i with i + Z[i] = n
Codeforces 432DPrefixes and SuffixesZ-array + counting to enumerate prefix-suffix matches
Codeforces 271DGood SubstringsZ-array of every suffix to count distinct substrings

12. Open Questions

  • Is there a “blocked” / cache-aware variant of the Z-algorithm that runs faster than the textbook version on modern hardware? KMP has a few; Z is rarer.
  • What is the cleanest constructive proof that the Z-array and the LPS array are O(n)-time inter-convertible? Gusfield gives an algorithm; many derivations sketch it but few prove it tightly.
  • Why does the Z-algorithm not generalise as cleanly to Aho-Corasick-style multi-pattern search as KMP does? The failure-link structure of KMP fits the trie naturally; the Z-algorithm’s [l,r] window does not.

13. See Also

Graph View

Backlinks