Z Algorithm Explained — Linear Time Pattern Matching with the Z Array

Algorithm Statement#

The Z algorithm preprocesses a string s of length n to produce a Z-array where Z[i] is the length of the longest substring starting at position i that is also a prefix of s. Pattern matching is performed by concatenating pattern + sentinel + text and scanning the Z-array for entries equal to the pattern length.

Definition: For string s, Z[i] = max k such that s[0..k-1] = s[i..i+k-1]. By convention Z[0] = n (the whole string matches its own prefix).

Example: s = "aabcaabxaaaz" produces Z = [12, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]. The 3 at index 4 means s[4..6] = "aab" matches the prefix s[0..2] = "aab".

Time complexity: O(n) construction, O(n + m) pattern matching. Space: O(n + m).

Why This Algorithm Matters#

Every interviewer who asks KMP secretly hopes you know the Z algorithm. It solves the same set of problems with a cleaner mental model: instead of a "longest proper prefix-suffix" array that requires fall-back logic, you get direct prefix-match lengths from every position. Google, Codeforces problem setters, and competitive programmers reach for Z first because the implementation fits in 10 lines and never has off-by-one bugs around fallback.

Z shines in problems where KMP feels awkward. Counting how many times each prefix of a string occurs as a substring, finding all positions where the pattern matches with a single sentinel concatenation, computing the period of a string, and solving "compare every suffix with a prefix" problems all collapse to a single Z-array scan. Companies like Amazon and Meta use these techniques inside log-mining pipelines and bioinformatics modules where billions of nucleotide reads must be aligned against reference genomes.

Strategically, mastering Z makes you fluent in the wider family of string algorithms. Manacher uses the same "rightmost interval" reuse pattern. Suffix automata generalise the prefix-matching idea. Once the Z mental model clicks, you read papers on suffix arrays and Lempel-Ziv compression without breaking stride.

The Core Insight#

The naive way to compute Z[i] is to compare s[0..] with s[i..] character by character — O(n^2) in the worst case on strings like "aaaaaa". The Z algorithm avoids this by remembering work it has already done.

We maintain a window [l, r] representing the rightmost Z-box discovered so far: an interval where s[l..r] matches s[0..r-l]. When we encounter a new index i:

1. If i is outside the window (i > r), we have no information to reuse. Compare characters starting from s[0] and s[i] until they diverge. Update [l, r] if the new match extends past r.
2. If i is inside the window (i <= r), the substring s[i..r] is identical to s[i-l..r-l] because s[l..r] mirrors s[0..r-l]. So we already know Z[i] is at least min(r-i+1, Z[i-l]). Only if that value reaches the right edge of the window do we attempt to extend by direct comparison.

The amortised cost is linear: every successful character comparison either advances r by one (and r never decreases), or we are inside a precomputed window and pay O(1).

Pattern matching uses a sentinel trick: build combined = pattern + '#' + text where # is a character not in either string. Compute Z over combined. Every position i where Z[i] = len(pattern) corresponds to a match of pattern in text starting at i - len(pattern) - 1. The sentinel guarantees no Z-value exceeds len(pattern), keeping matches well-defined.

Visual Dry Run#

String: s = "aabcaabxaaaz", length 12.

index:  0  1  2  3  4  5  6  7  8  9 10 11
char:   a  a  b  c  a  a  b  x  a  a  a  z
Z:     12  1  0  0  3  1  0  0  2  2  1  0

i = 1: Outside window (initially l = r = 0). Compare s[0]='a' with s[1]='a' (match), then s[1]='a' with s[2]='b' (mismatch). Z[1] = 1. Update window to [1, 1].

i = 2: Outside window. s[0]='a' vs s[2]='b' mismatches immediately. Z[2] = 0. Window unchanged.

i = 3: Same — Z[3] = 0.

i = 4: Outside window. Compare s[0]='a' with s[4]='a', s[1]='a' with s[5]='a', s[2]='b' with s[6]='b', s[3]='c' with s[7]='x' (mismatch). Z[4] = 3. Update window to [4, 6].

i = 5: Inside window since 5 <= 6. Mirror index is i - l = 1, so Z[i-l] = Z[1] = 1. Take min(r-i+1, Z[i-l]) = min(2, 1) = 1. Try to extend: s[1]='a' vs s[6]='b' mismatch. Z[5] = 1. Window unchanged.

i = 6: Inside window. Mirror is Z[2] = 0. Z[6] = 0.

i = 7: Outside window now (since r=6). s[0]='a' vs s[7]='x' mismatch. Z[7] = 0.

i = 8: Outside. s[0]='a' vs s[8]='a', s[1]='a' vs s[9]='a', s[2]='b' vs s[10]='a' mismatch. Z[8] = 2. Window becomes [8, 9].

The amortised total comparisons is at most 2n because the right edge r advances at most n times and explicit comparisons that fail also advance through at most n positions cumulatively.

Solution (Optimal)#

Python — Z Function and Pattern Search#

def z_function(s: str) -> list[int]:
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 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]
    return z
 
def z_search(text: str, pattern: str) -> list[int]:
    sentinel = '\x01'  # any char not in text or pattern
    combined = pattern + sentinel + text
    z = z_function(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] >= m]

JavaScript — Z Function and Pattern Search#

function zFunction(s) {
  const n = s.length;
  const z = new Array(n).fill(0);
  z[0] = n;
  let l = 0, r = 0;
  for (let i = 1; i < n; i++) {
    if (i < r) z[i] = Math.min(r - i, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] > r) { l = i; r = i + z[i]; }
  }
  return z;
}
 
function zSearch(text, pattern) {
  const sentinel = '
';
  const s = pattern + sentinel + text;
  const z = zFunction(s);
  const m = pattern.length;
  const matches = [];
  for (let i = m + 1; i < s.length; i++) {
    if (z[i] >= m) matches.push(i - m - 1);
  }
  return matches;
}

Complexity: O(n) construction. O(n + m) pattern matching. O(n) auxiliary space for the Z-array.

Common Mistakes#

Using r - i + 1 instead of r - i for the window length. Some references define r as the inclusive right edge while others use exclusive. Pick one convention and stick with it. The version above uses inclusive-exclusive: r is one past the last matched character. Mixing conventions creates off-by-one bugs that pass tiny tests but fail on patterns like "aaa".

Forgetting that Z[0] should be n, not 0. Some implementations skip Z[0] entirely. That works if you also skip it during pattern matching, but it makes the formal definition inconsistent. Set Z[0] = n explicitly to keep proofs and downstream code clean.

Choosing a sentinel that appears in the input. If your text contains #, using # as the separator allows false matches to bleed across the boundary. Use a character outside the alphabet — \x00 or \x01 for ASCII inputs, or a tuple-based combined sequence if you operate on arbitrary symbols.

Confusing Z with the LPS array of KMP. KMP's LPS gives the longest prefix-suffix at each position. Z gives the longest prefix-match starting at each position. They are duals — you can derive one from the other in linear time — but they are not the same array.

Re-comparing inside the window unnecessarily. The whole point of Z is that when Z[i-l] < r - i, you can copy the value verbatim without any character comparisons. Forgetting the min clamp turns the algorithm quadratic on inputs like "aaaa...aaab".

Interview Tips#

State the Z-array definition before writing code. Interviewers want to hear "Z[i] is the longest prefix of s that matches the suffix starting at i." From that one sentence the entire algorithm follows.

Compare Z to KMP out loud. Mention that Z and KMP are equivalent in power, both linear time, but Z has a flatter implementation with no fallback loops. For pattern matching, use the pattern + sentinel + text trick — interviewers love this because it shows you understand reductions.

If asked to compute the number of distinct substrings, count "occurrences as a prefix" of each suffix using Z over the reversed string, or pair it with a suffix array. Either way, Z gives you a building block.

When discussing complexity, emphasise the amortised argument: the right boundary r advances at most n times across the entire run, so the total work in the inner while loop is bounded by n. The outer for loop is also n, giving a clean O(n).

Follow-up Questions#

Q: How do you find the period of a string using Z? A: The smallest period p is the smallest index where i + Z[i] = n and p divides n. Equivalently, s[0..n-p-1] repeats n/p times. This is constant-time after computing Z.

Q: What is the largest Z-value, and what does it mean? A: It is the longest substring (other than the whole string) that matches a prefix. This appears in problems like "longest border" and "compress repeating prefixes."

Q: How do you count occurrences of every prefix in the string? A: Initialise cnt[Z[i]] for each i, then propagate cnt[i] += cnt[i+1] from right to left. Each prefix of length k occurs cnt[k] + 1 times (the +1 accounts for itself).

Q: Z vs Suffix Array — when to choose? A: Z is O(n) and trivial to code; suffix array is O(n log n) with more setup but answers a richer query family (lexicographic ranking, LCP, longest repeated substring). For one-shot pattern matching, Z. For repeated queries on a single text, suffix array.

Q: Can Z handle multi-pattern search? A: Not natively — it is built around a single reference prefix. For multi-pattern matching, use Aho-Corasick (covered in part 18 of this series).

Key Takeaways#

• The Z-array gives Z[i] equals the length of the longest substring at index i that matches a prefix, computed in linear time using a rightmost-window reuse trick.
• Pattern matching reduces to running Z on pattern + sentinel + text and reporting positions where Z[i] equals the pattern length.
• Z is equivalent to KMP in power and complexity, but the implementation is shorter and avoids fallback loops, making it a competitive-programming favourite.
• Common pitfalls are window-boundary off-by-one errors, choosing sentinels that appear in the input, and forgetting the min clamp that keeps the algorithm linear.
• Z generalises beautifully — period detection, prefix occurrence counts, and longest border all fall out of one Z-array scan.
• Interview signal: knowing Z alongside KMP shows depth in string algorithms, the kind expected at Google, Meta, and any team that touches text-processing infrastructure.