1. One-Liner
The Z-algorithm builds an array Z where Z[i] is the length of the longest common prefix between S and S[i..], in O(n) time.
2. The Problem It Solves
Needed for pattern matching (P#T), finding periods, string compression hints, and many string DS problems — anywhere you need repeated prefix–suffix structure in linear time.
3. The Core Idea
Maintain a Z-box [L, R] where S[L..R] matches S[0..R-L]. If i lies inside the box, you can copy a previous Z value (with a cap) instead of naively expanding.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Initialize Z[0]=n (or 0 by convention; implementations vary for i=0). |
| 2 | Maintain l, r for the furthest matched segment aligned with the prefix. |
| 3 | For i from 1 to n-1: if i > r, brute-expand; else Z[i] = min(r - i + 1, Z[i - l]). |
| 4 | If extension past r, update l, r. |
5. Dry Run Example
S = "aaaa". Classic Z (0-based, Z[0]=n or 0): Z[1]=3, Z[2]=2, Z[3]=1 — shows maximal overlaps at each shift.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
| Relation | Z ↔ prefix function (convertible) |
7. Where It Is Used
| Domain | Use |
|---|---|
| CP / interviews | Substring occurrences via P + '#' + T |
| Data compression | LZ-style reasoning |
| Bioinformatics | Repeat detection pipelines |
8. Interview Tips
Know the Z-box invariant and why min(r-i+1, Z[i-l]) is safe. Be ready to derive KMP’s LPS from prefix function.
9. Comparison with Other Algorithms
| Tool | Role |
|---|---|
| KMP LPS | Failure links for matching |
| Z-array | All overlaps with prefix at once |
| Hashing | Probabilistic alternative |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Implementation Example (PYTHON)
def z_function(s):
n = len(s)
z = [0] * n
if n == 0:
return z
z[0] = n
l = r = 0
for i in range(1, n):
if 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] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z