Z-Algorithm
The Z-array tells you, for every position i in a string, how many characters starting at i match the very beginning of the string. Building this array in O(n) enables pattern matching, finding repeated prefixes, and counting pattern occurrences — often with simpler code than KMP.
Table of contents
One question, every position
Imagine standing at each position i of a string and asking: "How long is the string that starts here and also matches the very beginning of the whole string?"
For s = "AABXAAB":
Position 0: "AABXAAB" — matches prefix of length 7 (the whole thing)
Position 1: "ABXAAB" — 'A' matches s[0]='A', but 'B' ≠ 'A' → length 1
Position 2: "BXAAB" — 'B' ≠ 'A' → length 0
Position 3: "XAAB" — 'X' ≠ 'A' → length 0
Position 4: "AAB" — 'A'='A', 'A'='A', 'B'='B' → matches "AAB" → length 3
Position 5: "AB" — 'A'='A', 'B' ≠ 'A' → length 1
Position 6: "B" — 'B' ≠ 'A' → length 0
Z = [7, 1, 0, 0, 3, 1, 0]
This is the Z-array. Position 0 is always set to the full length by convention (it would otherwise be ∞ — the entire string matches its own prefix).
The photocopier bookmark story
A real-life story
You are photocopying a document page by page. You've already marked (with a bookmark) the last page that matched your reference copy's first chapter. When you reach a new page, you check: "Is this page still inside the range I already matched?" If yes, use the earlier comparison result directly — skip re-reading. If the page is beyond the bookmark, extend character by character, updating the bookmark.
The Z-algorithm's [L, R] window is that bookmark. It records the rightmost Z-box (a substring that matches the string's prefix) found so far. Every new position either falls inside this known window (copy a cached answer) or extends it (do new character comparisons). Either way, each character is compared at most once across the full run → O(n).
The one idea to remember
The entire pattern in one sentence
The Z-algorithm maintains a window [L, R] representing the rightmost known Z-match; for each new position, it either copies a cached value from inside the window (O(1)) or extends the window with new comparisons — ensuring each character is touched at most twice total, achieving O(n) time.
Building the Z-array
def z_function(s: str) -> list[int]:
n = len(s)
z = [0] * n
z[0] = n # convention: Z[0] = length of string
L, R = 0, 0 # [L, R] = rightmost Z-box found so far
for i in range(1, n):
if i < R:
# i is inside the known Z-box [L, R]
# s[i..R] matches s[i-L..R-L], so z[i] >= min(z[i-L], R-i)
z[i] = min(z[i - L], R - i)
# extend from max(z[i], 0) more characters
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
# update the rightmost Z-box if we extended beyond R
if i + z[i] > R:
L, R = i, i + z[i]
return z
Line-by-line narration:
z[0] = n— convention; avoids infinite loop since z[0] would extend to cover the whole string.if i < R— we're inside a previously discovered Z-box. Usez[i - L](the mirror position inside the box) but cap atR - i(can't trust beyond the box boundary).while— extend with new character comparisons. This loop is the only place actual comparisons happen.if i + z[i] > R— we pushed the boundary of our knowledge rightward; update the bookmark.
Frame-by-frame: s = "AABXAAB"
z[0] = 7 (convention)
i=1: not inside box (R=0). Compare s[0]='A' vs s[1]='A' → match, z[1]=1.
Compare s[1]='A' vs s[2]='B' → no match. z[1]=1. Update L=1, R=2.
i=2: i < R? 2 < 2? No. Compare s[0]='A' vs s[2]='B' → no match. z[2]=0.
i=3: i < R? No. Compare s[0]='A' vs s[3]='X' → no match. z[3]=0.
i=4: i < R? No. Compare s[0]='A' vs s[4]='A' → match. z[4]=1.
Compare s[1]='A' vs s[5]='A' → match. z[4]=2.
Compare s[2]='B' vs s[6]='B' → match. z[4]=3.
Out of bounds. z[4]=3. Update L=4, R=7.
i=5: i < R? 5 < 7? Yes. Mirror position: i-L = 5-4 = 1. z[1]=1, R-i=2.
z[5] = min(1, 2) = 1. Can we extend? s[1]='A' vs s[6]='B' → no. z[5]=1.
i + z[5] = 6 ≤ R = 7, no update.
i=6: i < R? 6 < 7? Yes. Mirror: i-L=2. z[2]=0, R-i=1.
z[6] = min(0, 1) = 0. Extend? s[0]='A' vs s[6]='B' → no. z[6]=0.
Z = [7, 1, 0, 0, 3, 1, 0] ✅
Notice: at i=5, we reused z[1]=1 instead of re-comparing — that is the caching benefit.
Application: Pattern matching using Z
To find all occurrences of pattern p in text t:
- Form
combined = p + "$" + t(the$is a separator that can't appear in either — ensures the Z-values in thetportion never exceedlen(p)) - Build Z-array for
combined - All positions
iincombinedwherez[i] == len(p)are matches; the start intisi - len(p) - 1
def z_search(text: str, pattern: str) -> list[int]:
m = len(pattern)
combined = pattern + "$" + text
z = z_function(combined)
return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
Why the $ separator? Without it, Z-values in the t portion could extend into the p portion and exceed m, giving wrong counts. The sentinel character guarantees z[i] <= m everywhere in the t region.
KMP vs Z-Algorithm
| Aspect | KMP | Z-Algorithm |
|---|---|---|
| Core precomputed structure | Failure function (fail[i]) | Z-array (z[i]) |
| Meaning of value | Longest proper prefix-suffix at i | Length of match with full string starting at i |
| Code complexity | Trickier (fall-back logic) | Simpler (one while loop) |
| Memory | O(m) | O(n + m) for combined string |
| Both achieve | O(n + m) pattern matching | O(n + m) pattern matching |
Choose Z when you want simpler code. Choose KMP when you're asked specifically about it, or need to avoid allocating the combined string.
Common traps
Watch out for these
- Forgetting the
$separator. Without it, Z-values in the text portion can overflowm, causing false positives. - Setting
z[0] = 0instead ofn. If you treat z[0] as 0, your[L, R]window never starts correctly. By convention,z[0] = len(s). - Using
i <= Rinstead ofi < R. The Z-box is[L, R)— R is exclusive in the code above. Be consistent with your convention. - Forgetting to update
[L, R]only wheni + z[i] > R. If the new Z-value doesn't extend beyond R, the window doesn't grow — don't update L and R.
Remember this forever
Z-Algorithm
z[0] = n; L, R = 0, 0
for i in range(1, n):
if i < R: z[i] = min(z[i - L], 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]
Pattern matching: combined = p + "$" + t, find positions where z[i] == len(p).
Trap: always include $ separator, always set z[0] = n.
Check yourself
Why does the Z-algorithm run in O(n) even though there's a `while` loop inside the `for` loop?
The while loop only runs when it extends z[i] beyond the current right boundary R. Each extension increments R by at least 1. Since R can increase at most n times (it's bounded by the string length), the while loop body executes at most n times total across all iterations of the for loop. The for loop itself runs n - 1 times. Total operations: O(n).
Why use a `$` separator character that doesn't appear in either string?
Z-values in the text portion of p + "$" + text should be at most len(p) — a full match of the pattern. If $ is not used and a character in text can match a character in p beyond position m-1, the Z-value could exceed m, falsely indicating a longer match than the pattern. The sentinel stops all Z-comparisons at the boundary between pattern and text.
Practice problems
| Problem | Difficulty | What to notice | Link |
|---|---|---|---|
| String Matching in an Array | Medium | Z-search each word against each pattern | LC #1408 |
| Implement strStr() | Easy | Z-algorithm alternative to KMP | LC #28 |
| Repeated Substring Pattern | Easy | Z-trick: same as KMP approach | LC #459 |
Next up: Palindrome — Expand Around Center — finding the longest palindromic substring in O(n²) by expanding outward from every center.