Z-Function

The Z-function tells you, for every position of a string, how far it agrees with the string's own beginning. One linear pass gives you pattern search, periods and borders, and many people find it easier to remember than KMP.

advanced⏱ 10 min read

←Builds on

11Prefix Function & KMPThe Z-function measures matches with the string's start, just as the prefix function measures borders.1Prefix Sums, Two Pointers & Sliding WindowIt keeps a window [l, r] of the rightmost match to skip comparisons it already made.

Leads to→

+Manacher's AlgorithmManacher reuses the Z-function's rightmost window to start each center from a known answer.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01What z[i] means

z[i] is the length of the longest common prefix of the whole string s and its suffix s[i..]. In other words: start reading at i and at 0 at the same time, and count how many characters agree.

For s = AABAAAB you get z = [0, 1, 0, 2, 3, 1, 0]. For example z[4] = 3, because s[4..6] = AAB matches the first three characters AAB. By convention z[0] = 0 (some write n).

Computing every z[i] by direct comparison is O(n²) in the worst case, for example on AAAA…A. The real algorithm reuses work and gets O(n).

02The z-box: reuse what you matched

Keep the z-box [l, r): the match with a prefix that reaches furthest to the right. Inside it, s[l..r) is a copy of s[0..r−l). So for a position i inside the box, its mirror is i − l near the start, and you already know z[i − l].

If i < r: start from z[i] = min(r − i, z[i − l]). The min stops you from trusting anything beyond the box edge.
Otherwise start from 0.
Then extend by direct comparison, and if the match passes r, move the box to [i, i + z[i]).

Every successful extra comparison pushes r right, and r never moves left. So the total work is O(n), the same amortized argument as in KMP.

03Pattern search with P#T

To find a pattern P in a text T, build P + "#" + T, where # is a character that appears in neither string, and compute its Z-function. Wherever z[i] = |P|, the pattern occurs in T at position i − |P| − 1.

The separator matters: it stops a match from running past the end of P, so no z value can exceed |P|.

The Z-function and the prefix function carry the same information and can be converted into each other. Choose whichever you find easier to write without bugs. Z also gives the periods of a string directly: p is a period if z[p] = n − p.

Cost at a glance

Z-functionO(n)

Pattern search (P#T)O(n + m)

MemoryO(n + m)

Remember

z[i] is the length of the longest common prefix of s and s[i..].
Inside the z-box, start from the mirrored value min(r − i, z[i − l]); since r only moves right, the whole run is O(n).
Run Z on P + "#" + T: every z[i] = |P| is an occurrence of the pattern.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the highlighted z-box: when i lands inside it, z[i] starts from a copied value instead of zero.

Interactive visualizerfocus here, then space ← →

Z-function

AABAAAB

z[]

	A	A	B	A	A	A	B
z	0	·	·	·	·	·	·

The Z-function: z[i] = length of the longest substring starting at i that is also a prefix of the whole string. Maintain a “z-box” [l,r]: the match reaching furthest right.

Pseudocode

 1 z[0] = 0; maintain a z-box [l,r] = rightmost match with a prefix 2 if i < r: z[i] = min(r-i, z[i-l])     // mirror inside the box 3 else: z[i] = 0 4 extend z[i] by explicit comparisons; push [l,r] right if it grows

1 / 1

Check

Three questions. Pick an answer to see why.

What is the Z-function of "ABAB" (with z[0] = 0)?

The z-box is [l, r) = [4, 9), and z[1] = 6. What is the starting value for z[5]?

Why do we put a separator # between P and T?

Practice

Real problems to lock it in, easiest first.

CSESString Matching beginner↗CSESFinding Borders intermediate↗CSESString Functions intermediate↗LeetCodeSum of Scores of Built Strings advanced↗