Z-algorithm
- Algorithms course
- Expert
- Lesson 16/41
- 4 min
Match positions with the Z-function.
Z-algorithm
The Z-algorithm computes the Z-array for each position of a string. Z[i] is the length of the longest common prefix between the string and its suffix starting at position i.
For example, for "aabxaab" we get Z = [0, 1, 0, 0, 3, 1, 0]. Z-values are used in pattern matching, repeat detection and compression.
The algorithm runs in linear time, O(n), and maintains an [L, R] window with two pointers.
Z window
The Z-algorithm maintains an [L, R] window where R is the farthest position reached by a match. For a new i, if i is beyond R we compare naively.
If i is within R, Z[i] is at least min(Z[i-L], R-i+1). This lets us reuse previous Z-values.
R is updated whenever the window extends; the total work is O(n).
Practice z_function function
Write z_function(s). Return the Z-array of the string. Print [0, 1, 0, 0, 3, 1, 0] with print(z_function("aabxaab")).
Starter code
def z_function(s):
# Compute the Z-arraySample solution
def z_function(s):
# Compute the Z-array
n = len(s)
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 = i
R = i + z[i] - 1
return z
print(z_function("aabxaab"))Expected output
[0, 1, 0, 0, 3, 1, 0]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does Z[i] represent?
s = "aabxaab"- Longest common prefix of start and i-th suffix Correct answer
- Length of the string
- ASCII value of the i-th character
- Number of matches after i
Explanation: Z[i] is the longest common prefix of start and i-th suffix.
2 Z-array start
z = [0] * n
____ = 0
L = R = 0z = [0] * n
z[0] = 0
L = R = 0Explanation: z[0] is conventionally 0.
3 Z concepts
| Term | Meaning |
|---|---|
Z[i] |
Common prefix length |
[L, R] |
Window |
O(n) |
Linear time |
z[0] |
Conventionally zero |