Z-algorithm

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).

Exercise 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")).

Show example 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"))

Test yourself

What does Z[i] represent?
```
s = "aabxaab"
```
- Longest common prefix of start and i-th suffix
- Length of the string
- ASCII value of the i-th character
- Number of matches after i
Show answer

Longest common prefix of start and i-th suffix — Z[i] is the longest common prefix of start and i-th suffix.

Z-array start

z = [0] * n
____ = 0
L = R = 0

Show answer

z = [0] * n
z[0] = 0
L = R = 0

Z concepts

Z[i]

Common prefix length
[L, R]

Window
O(n)

Linear time
z[0]

Conventionally zero

Next lesson: Suffix array

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies