Z Function
Z Function Algorithm Leetcode: 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.
- 1 <= |s| <= 10⁵
- s consists of lowercase English letters
- Z[0] is conventionally left as 0 or set to |s|
Intuition
The z function algorithm leetcode problem computes, for every position i, the length of the longest substring starting at i that also matches a prefix of the string. Comparing naively from each position is O(n²); the Z-algorithm does it in O(n) by reusing what earlier positions already proved.
The reuse works through a Z-box — the rightmost interval [l, r] discovered so far that is known to match a prefix. That is not a bookkeeping detail; it is the entire idea. If s[l..r] equals s[0..r−l], then any position i inside that window has a mirror at i − l in the prefix, and the answer at the mirror is already computed.
So for i inside the box you get a head start for free:
- Z[i] starts at min(Z[i − l], r − i + 1).
The cap matters. Beyond r nothing is known to match, so the mirror's value cannot be trusted past the window edge — copying it wholesale is the classic bug.
From that starting point, extend by direct character comparison past r. Every such comparison that succeeds pushes r further right, and r never moves backwards, so the total number of comparisons across the whole run is bounded by n. That is why the algorithm is linear despite the inner loop.
For pattern matching, run it on pattern + '$' + text and every Z value equal to the pattern length marks an occurrence.
The Z-array gives, for each position, the length of the longest prefix match starting there — and it's built in linear time by reusing work. The [l, r] window is a previously-matched block: inside it, an earlier Z-value predicts the answer for free, so comparisons only ever extend past r. That reuse-what-you-matched idea is the same one behind KMP.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(n) space.
Understand what the Z-box guarantees
The interval [l, r] is the rightmost known match of a prefix: s[l..r] == s[0..r-l]. Everything the algorithm reuses comes from this equality, so keeping it accurate is what keeps the results correct.
Copy the mirrored value inside the box
For i within [l, r], the mirror position is i - l. Start Z[i] at Z[i - l], which is already known — this is the step that avoids re-comparing characters that an earlier position already matched.
Cap the copy at the box edge
Take min(Z[i - l], r - i + 1). Beyond r the match is unverified, so the mirror's value cannot be trusted there. Copying without the cap is the standard bug and produces values longer than the actual match.
Extend past r by direct comparison
From the starting value, compare characters at i + Z[i] against Z[i] and increment while they match. Only comparisons beyond r do new work — everything before it was settled by the copy.
Update the box when the match reaches further
If i + Z[i] - 1 exceeds r, set l = i and r = i + Z[i] - 1. The box always tracks the rightmost verified match, which is what keeps future positions inside it as often as possible.
Use it for pattern matching
Build the Z-array of pattern + '$' + text, where $ appears in neither. Any position whose Z value equals the pattern length is an occurrence — the separator prevents matches from spanning the boundary.
Cost of the linear scan
r only ever moves right and every extending comparison advances it, so the total comparison count is O(n), giving O(n) time and O(n) space for the Z-array.
Solution & live demo
Common pitfalls
Comparing from scratch at every position
for i in range(1, n):
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1That's the O(n²) version — correct, but it re-derives matches already known. Inside the [l, r] window the text mirrors the prefix, so a previous Z-value gives a free starting length.
Omitting the r - i + 1 cap
z[i] = z[i - l]
z[i] = min(r - i + 1, z[i - l])
The mirrored value is only trustworthy as far as the window extends. Copying it wholesale asserts matches beyond r that were never verified, and the result is silently too large.
Starting the loop at index 0
for i in range(n):
for i in range(1, n):
z[0] would be the whole string matching itself, which is conventionally left as 0 and, worse, would set r to n - 1 immediately — making every later position think it sits inside a verified window.
Edge cases
Z = [-, n−1, n−2, …] — windows chain perfectly, still linear.
'$ must not appear in either string, guaranteeing no match spans it.