Z-Algorithm

For every position in a string, ask: “how many characters starting here match the beginning of the string?” Computing that naively is O(n²) — re-scan from each position. But here’s the leverage: once you’ve matched a long stretch starting at some position, you already know what the characters inside it are — they equal a prefix you’ve seen. So for positions inside that stretch, you can read the answer off a mirror instead of re-comparing. That one observation collapses O(n²) to O(n), and it’s the cleanest such argument in all of string matching.

The Z-algorithm constructs an array Z where Z[i] is the length of the longest substring starting at position i that is also a prefix of the whole string. With this array in hand, finding a pattern in a text becomes a single linear scan.

It’s arguably the cleanest of the three linear matchers: one array, one linear scan, a clear loop invariant. Many competitive programmers prefer it over KMP precisely because the code is shorter and easier to remember.

The Z-array

For a string S of length n, define:

Z[0] = n   (by convention, or sometimes left as 0)
Z[i] = length of the longest string starting at S[i] that matches a prefix of S

Example: S = "AABXAABXCAABXAABXAY"

The Z-array is [19, 1, 0, 0, 4, 1, 0, 0, 0, 8, 1, 0, 0, 4, 1, 0, 0, 1, 0].

Notice Z[9] = 8: the suffix starting at position 9 shares an 8-character prefix with the full string. That means S[9..16] == S[0..7] — a useful structural fact.

Constructing the Z-array: the Z-box trick

The naive approach — for each i, count matching characters from position i and from 0 — is O(n²) in the worst case. The Z-algorithm maintains a Z-box: the interval [l, r] corresponding to the rightmost Z-value computed so far. Specifically, S[l..r] is the window that was matched to produce the current rightmost known prefix extension.

The loop invariant: S[l..r] == S[0..r-l] (i.e., the substring S[l..r] matches the prefix S[0..r-l]).

For each position i:

• Case 1: i > r — i is outside the current Z-box. We have no free information. Start comparing S[i] with S[0], S[i+1] with S[1], etc. Update [l, r] if we find a match.
• Case 2: i <= r — i is inside the Z-box. Since S[l..r] == S[0..r-l], position i corresponds to position i - l inside the prefix. We know Z[i-l] characters match from there.
  • Sub-case 2a: Z[i-l] < r - i + 1 (the known match doesn’t reach the Z-box boundary). Then Z[i] = Z[i-l] — exactly as much match as the interior position, no extension needed.
  • Sub-case 2b: Z[i-l] >= r - i + 1 (the known match reaches or exceeds the boundary). Then Z[i] >= r - i + 1, and we try to extend further from r + 1.

In both sub-cases of Case 2, we either directly read off Z[i] or start extending from a position we’ve already reached. The r pointer never decreases. Since r increases by at most n total across all iterations, the total work is O(n).

Implementation

vector<int> zArray(const string& S) {
    int n = S.size();
    vector<int> Z(n, 0);
    Z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) Z[i] = 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;
}
 
vector<int> zSearch(const string& T, const string& P) {
    string S = P + "#" + T;     // '#' must not appear in T or P
    auto Z = zArray(S);
    int m = P.size();
    vector<int> matches;
    for (int i = m + 1; i < (int)S.size(); i++)
        if (Z[i] == m)
            matches.push_back(i - m - 1);
    return matches;
}

def z_array(S):
    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(T, P):
    S = P + "#" + T        # '#' sentinel separates P from T
    Z = z_array(S)
    m = len(P)
    return [i - m - 1 for i in range(m + 1, len(S)) if Z[i] == m]

int[] zArray(String S) {
    int n = S.length();
    int[] Z = new int[n];
    Z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) Z[i] = Math.min(r - i, Z[i - l]);
        while (i + Z[i] < n && S.charAt(Z[i]) == S.charAt(i + Z[i]))
            Z[i]++;
        if (i + Z[i] > r) { l = i; r = i + Z[i]; }
    }
    return Z;
}
 
List<Integer> zSearch(String T, String P) {
    String S = P + "#" + T;
    int[] Z = zArray(S);
    int m = P.length();
    List<Integer> matches = new ArrayList<>();
    for (int i = m + 1; i < S.length(); i++)
        if (Z[i] == m) matches.add(i - m - 1);
    return matches;
}

The entire Z-box optimization is one line. When i falls inside the current box [l, r], you don’t compare from scratch — you copy the mirror value Z[i - l], capped so it can’t claim more than the box guarantees. Rebuild that line:

def z_array(S):
  n = len(S)
  Z = [0] * n
  Z[0] = n
  l = r = 0
  for i in range(1, n):
      # ??? copy the mirror's Z-value, but never past the box edge (r - 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

min(r - i, Z[i - l]): the mirror position i - l already told us its match length, but we can only trust it up to the box edge r - i — past that, the box invariant says nothing, so we cap and then extend by hand in the while. Drop the min and you’d over-claim matches the box never verified.

Why the concatenation trick works

When we form S = P + "#" + T, the Z-values in the T portion tell us exactly how many characters of T[i..] match a prefix of S — which is the same as a prefix of P (since "#" can’t appear in either, it caps all Z-values at m). If Z[m + 1 + i] == m, then T[i..i+m-1] == P[0..m-1] — a full match.

The "#" separator is critical: without it, the pattern characters might blend into the text characters and inflate Z-values spuriously.

Applications

String periodicity

A string s has period p if s[i] == s[i+p] for all valid i. The Z-array directly exposes this:

def find_period(s):
    Z = z_array(s)
    n = len(s)
    for p in range(1, n):
        if Z[p] >= n - p:    # S[p..n-1] matches S[0..n-p-1]
            return p
    return n                 # period is the full length (no repetition)

If Z[p] >= n - p, then every suffix of s starting at a multiple of p matches the prefix — the string has period p.

Counting distinct substrings with suffix arrays

The Z-array on each suffix can count how many of its characters are “new” (not overlapping with any shorter suffix match). This is the core idea behind the LCP array in suffix arrays — but that’s covered in Advanced Patterns.

Z vs KMP vs Rabin-Karp

For a clean interview implementation of single-pattern search, Z-algorithm is often the quickest to write correctly. For the structural application (failure function, Aho-Corasick, palindrome tricks), KMP’s failure function is more useful.

Complexity

Quick check

The Z-box’s “trust the mirror, but only inside the verified window” is the same move you’ll see again immediately — Manacher’s palindrome algorithm is the Z-box with palindromes instead of prefixes. KMP, Rabin-Karp, and Z now give you three complete answers to single-pattern search. Next: Advanced Patterns — Manacher’s O(n) palindromes, the Aho-Corasick multi-pattern machine, and a sketch of suffix arrays, for the problems one pattern can’t cover.