GeeksforGeeks Medium

Z Function

Compute Z[i] = length of the longest substring starting at i that matches a prefix of s, in O(n). Search patterns via pat$txt.

stringz-algorithmpattern-matching

Open on GeeksforGeeks ↗

02

Intuition

💡

Maintain the rightmost match window [l, r] found so far (a segment known to equal a prefix). Inside it, position i mirrors position i−l of the prefix — copy Z[i−l] for free, capped at the window edge; only extend by direct comparison past r. Every comparison pushes r right, so total work is linear.

03

Approach

1

The Z-box [l, r]

s[l..r] equals s[0..r−l]. For i inside it, the answer is already partially known from the prefix's own Z values.

2

Copy, cap, extend

Z[i] = min(Z[i−l], r−i+1) as a starting point; then compare characters beyond r to extend. Update [l, r] if i's match reaches further right.

3

Pattern search

Build Z on pat + '$ + txt: any Z value equal to len(pat) marks a full occurrence.

04

Solution & live demo

python

▶1def z_function(s):
▶2    n = len(s)
▶3    z = [0] * n
▶4    l = r = 0
▶5    for i in range(1, n):
▶6        if i <= r:
▶7            z[i] = min(r - i + 1, z[i - l])
▶8        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
▶9            z[i] += 1
▶10        if i + z[i] - 1 > r:
▶11            l, r = i, i + z[i] - 1
▶12    return z

05

Edge cases

All same characters

Z = [-, n−1, n−2, …] — windows chain perfectly, still linear.

Separator character

'$ must not appear in either string, guaranteeing no match spans it.

06

Complexity

Time

O(n)

Space

O(n)

r only moves right → amortized linear.