StringsAlgorithmaka Z-function, Z-array, Z-boxes

Z-Algorithm

Compute for every position the length of the longest substring starting there that matches a prefix of the string, in linear time.

▶ VisualizePattern: Sliding WindowPractice (1)
Progress

Overview

The Z-function of a string s is an array where z[i] is the length of the longest substring starting at i that is also a prefix of s (with z[0] conventionally 0 or n). For s = "aabaaab", z = [0, 1, 0, 2, 3, 1, 0]: at index 4 the substring "aab" matches the prefix "aab".

Pattern matching follows immediately: build the Z-array of p + "$" + t for a separator $ absent from both. Every index in the text part with z[i] == m is an occurrence. The algorithm runs in O(n + m) and is often easier to reason about than Knuth–Morris–Pratt (KMP) because z[i] has a direct definition rather than an amortised one.

pattern matchingZ-functionO(n)prefix matchesborders

Intuition

A mental model before the formal terms.

Picture the string laid out with a highlighter. Whenever a substring starting at i matches the prefix, you draw a Z-box [l, r] covering it. Now consider a position i inside the rightmost box. Because the box is a copy of the prefix, position i in the box corresponds to position i - l in the prefix — and you already computed z[i - l]. So you can read off a guaranteed match length for free, and only need to compare characters beyond the box's right edge.

How it works

  1. Maintain the rightmost Z-box [l, r] seen so far (initially empty, l = r = 0).
  2. For i from 1 to n - 1: if i < r, initialise z[i] = min(r - i, z[i - l]) — the mirrored value from the prefix, capped so it does not run past the known box.
  3. Extend by brute force: while i + z[i] < n and s[z[i]] == s[i + z[i]], increment z[i].
  4. If i + z[i] > r, the new box reaches further right: set l = i, r = i + z[i].
  5. To search, run this on p + "$" + t and report every i > m with z[i] == m, giving text index i - m - 1.

Why it works

Inside the box [l, r), the string s[l..r) equals s[0..r-l). Hence s[i..r) equals s[i-l..r-l), so the substring at i matches the prefix for at least min(z[i-l], r - i) characters. That initial value is always a valid lower bound, and the brute-force extension only compares characters at or beyond r.

Every character comparison that succeeds pushes r to a new maximum, and r never decreases; every comparison that fails ends the extension for the current i. So there are at most n successful and n failed comparisons: O(n) total.

Recognition

How to tell a problem wants this.

  • You need, for every position, how far the string matches its own prefix — e.g. "for each suffix, longest common prefix with the whole string".
  • Pattern search where you want a plain array answer instead of KMP's state machine.
  • Period, border and "string compression" questions: n - z[i] relationships reveal the smallest period.
“contiguous subarray” → Sliding Window

Interactive visualization

Play, step, change the input. ← → and space work too.

a
a
0
b
1
c
2
a
3
b
4
y
5
$
6
a
7
b
8
x
9
a
10
b
11
c
12
a
13
b
14
c
15
a
16
b
17
y
18
z
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1/38Concatenate pattern + '$' + text (the '$' separator never matches, so no z-value exceeds 6). z[i] = length of the longest substring starting at i that is also a prefix of s.
Current position iCharacters being extendedz[i] == |pattern|: matchCurrent Z-box [l, r]
PseudocodeLearn Z-Algorithm →
1s = pattern + "$" + text; z[0] = 0; l = r = 0
2for i in 1 .. len(s)-1:
3  if i <= r: z[i] = min(r - i + 1, z[i - l])   # reuse the Z-box
4  while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]: z[i] += 1
5  if i + z[i] - 1 > r: l = i; r = i + z[i] - 1
6  if z[i] == m: report match at i - m - 1
Variables
l0
r0
m6
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(n + m)
Speed

Pseudocode

1z[0] = 0, l = r = 0
2for i in 1 .. n-1:
3  if i < r: z[i] = min(r - i, z[i - l])
4  while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1
5  if i + z[i] > r: l = i, r = i + z[i]

Implementations

1def z_function(s: str) -> list[int]:
21 · Initialize Z-array and rightmost box
3    n = len(s)
4    z = [0] * n
5    l = r = 0  # rightmost Z-box is [l, r)
6    for i in range(1, n):
72 · Mirror the value inside the box
8        if i < r:
9            z[i] = min(r - i, z[i - l])
103 · Extend past the box by direct comparison
11        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
12            z[i] += 1
134 · Push the box's right edge
14        if i + z[i] > r:
15            l, r = i, i + z[i]
16    return z
17 
18 
19def z_search(text: str, pattern: str) -> list[int]:
205 · Search via pattern + separator + text
21    m = len(pattern)
22    if m == 0 or m > len(text):
23        return []
24    z = z_function(pattern + "\x00" + text)  # NUL occurs in neither string
25    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] == m]
Walkthrough
  1. z = [0] * n and the tuple assignment l, r = i, i + z[i] are the idiomatic ways to initialise and update the box.
  2. The if i < r mirror step reads z[i - l], a value already computed because i - l < i.
  3. The while loop performs the only character comparisons; each success extends r, which never decreases — the O(n) argument.
  4. pattern + "\\x00" + text builds one combined string; Python strings are immutable, so this is a single O(n + m) copy, not repeated appends.
  5. The list comprehension converts combined indices to text indices with i - m - 1.
Complexity (this implementation)
time O(n + m) · space O(n + m)

The concatenation copies both strings once; building the combined string with repeated += in a loop would be quadratic.

Language notes
  • "\\x00" is an ordinary one-character Python string — safe as a separator because Python strings are not NUL-terminated.
  • Variable names l and r mirror the literature; flake8 warns about the ambiguous name l, so rename to left in linted codebases.
  • For very large inputs consider bytes instead of str: indexing bytes yields small ints and avoids one-character string objects.
Common mistakes in this language
  • Starting the loop at i = 0; z[0] must stay 0 (or be handled specially) or the mirror lookups are corrupted.
  • Writing z[i] = min(r - i, z[i - l]) without the i < r guard, which reads a stale box.
  • Using a printable separator like "#" for inputs that may contain it.
Language differences that matter here
  • Separator safety: all four languages allow an embedded NUL in their string type (std::string is length-counted, JS/TS use \u0000, Python "\x00"); only C-style char* APIs in C++ would truncate at it.
  • Concatenation cost: pattern + sep + text copies the text once in every language — Python and JS/TS because strings are immutable, C++ because a new std::string is built. KMP avoids the copy entirely.
  • Character comparison units: C++ compares bytes, JS/TS UTF-16 code units, Python Unicode code points; the algorithm is unit-agnostic as long as pattern and text use the same encoding.
  • The Z-array is n + m + 1 small integers: std::vector<int>, packed SMI arrays in JS/TS, a Python list of ints (about 8 bytes vs 28+ bytes per element).

Complexity

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)

Needs the concatenated string in memory; KMP is preferable for streams.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • You need the full array of "prefix match lengths" for every position, not just occurrences.
  • Pattern matching with a simple, deterministic linear algorithm and no state-machine reasoning.
  • Period/border problems: the smallest p with p + z[p] == n is the period of the string.
Avoid it when

Alternatives

Knuth–Morris–Pratt (KMP)Rabin–KarpNaive String Matching

Common mistakes

  • Forgetting to cap the mirrored value with r - i — the Z-box only guarantees characters up to r.
  • Using i <= r with an exclusive r (or i < r with an inclusive r); be consistent about whether r is the first index past the box.
  • Choosing a separator that can appear in the text or pattern, so z values leak across the boundary.
  • Starting the loop at i = 0 and letting z[0] = n corrupt the mirror lookups.

Interview patterns

  • Find all occurrences of p in t via z(p + "$" + t).
  • Number of distinct prefixes that appear elsewhere in the string.
  • Shortest palindrome / longest palindromic prefix using z(rev(s) + "$" + s).
  • Smallest period of a string (string compression).
Interview questions on this
Mock interviews

Example problems

Find the Index of the First Occurrenceeasy