Z-Algorithm for Linear-Time String Matching

---

What is the Z-Array?

Given a string S of length n, the Z-array Z[0..n-1] is defined as:

Z[i] = the length of the longest substring starting at position i that matches a prefix of S.

By convention, Z[0] is undefined (or set to 0 or n, depending on the implementation) since the entire string trivially matches itself.

Example

For S = "aabxaab":

i	0	1	2	3	4	5	6
S	a	a	b	x	a	a	b
Z	-	1	0	0	3	1	0

• Z[1] = 1: Starting at index 1, “a” matches the prefix “a” (but “ab” != “aa”).
• Z[4] = 3: Starting at index 4, “aab” matches the prefix “aab”.
• Z[2] = 0: Starting at index 2, “b” does not match “a” (the first character of the prefix).

---

Naive Z-Array Construction (O(n^2))

def z_array_naive(s):
    """Compute Z-array in O(n^2) -- for understanding only."""
    n = len(s)
    z = [0] * n
    
    for i in range(1, n):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
    
    return z


s = "aabxaab"
print(z_array_naive(s))  # [0, 1, 0, 0, 3, 1, 0]

This is O(n^2) in the worst case (e.g., “aaaaa”).

---

Linear-Time Z-Algorithm: The Z-Box

The Z-algorithm maintains a Z-box [l, r] which is the rightmost interval [l, l + Z[l] - 1] that has been computed so far and extends the farthest to the right.

The Algorithm

For each position i:

1. Case 1: i {'>'} r — i is outside the Z-box. Compute Z[i] from scratch by comparing characters.

2. Case 2: i {'<'}= r — i is inside the Z-box. We know that S[i..r] matches S[i-l..r-l]. Let k = i - l. We have two sub-cases:

   • 2a: Z[k] {'<'} r - i + 1 — The previous match at position k does not reach the end of the Z-box. So Z[i] = Z[k] (we can reuse it directly).
   • 2b: Z[k] {'>'}= r - i + 1 — The match might extend beyond the Z-box. Start extending from r + 1.

After computing Z[i], update the Z-box if i + Z[i] - 1 {'>'} r.

Implementation

def z_function(s):
    """Compute Z-array in O(n) using the Z-box optimization."""
    n = len(s)
    if n == 0:
        return []
    
    z = [0] * n
    z[0] = n  # By convention
    
    l, r = 0, 0  # Z-box [l, r]
    
    for i in range(1, n):
        if i < r:
            # Case 2: inside Z-box
            k = i - l
            if z[k] < r - i:
                # Case 2a: stays within Z-box
                z[i] = z[k]
                continue
            else:
                # Case 2b: might extend beyond
                z[i] = r - i
        
        # Extend from z[i] (either from 0 or from r-i)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        
        # Update Z-box if this extends further right
        if i + z[i] > r:
            l = i
            r = i + z[i]
    
    return z


# Test cases
print(z_function("aabxaab"))       # [7, 1, 0, 0, 3, 1, 0]
print(z_function("aaaaa"))         # [5, 4, 3, 2, 1]
print(z_function("aabaab"))        # [6, 1, 0, 3, 1, 0]
print(z_function("abcabcabc"))     # [9, 0, 0, 6, 0, 0, 3, 0, 0]

Why is This O(n)?

Each character comparison either:

• Extends the Z-box to the right (this can happen at most n times total since r only increases), or
• Reuses a previously computed value without any character comparisons.

So the total number of character comparisons is O(n).

---

Pattern Matching Using Z-Algorithm

The Trick: Concatenation

To find pattern P in text T:

1. Create S = P + "$" + T where $ is a character not in P or T.
2. Compute the Z-array of S.
3. For any index i {'>'} len(P), if Z[i] == len(P), then the pattern starts at position i - len(P) - 1 in T.

def z_search(text, pattern):
    """Find all occurrences of pattern in text using Z-algorithm."""
    concat = pattern + "$" + text
    z = z_function(concat)
    
    m = len(pattern)
    results = []
    
    for i in range(m + 1, len(concat)):
        if z[i] == m:
            results.append(i - m - 1)  # Position in original text
    
    return results


# Examples
text = "abcabcabc"
pattern = "abc"
print(f"'{pattern}' found at: {z_search(text, pattern)}")
# 'abc' found at: [0, 3, 6]

text2 = "aaaaaaa"
pattern2 = "aaa"
print(f"'{pattern2}' found at: {z_search(text2, pattern2)}")
# 'aaa' found at: [0, 1, 2, 3, 4]

text3 = "hello world hello"
pattern3 = "hello"
print(f"'{pattern3}' found at: {z_search(text3, pattern3)}")
# 'hello' found at: [0, 12]

---

Application: Finding the Period of a String

A period of string S is the smallest length p such that S is a prefix of some repetition of S[0..p-1].

For example:

• "abcabc" has period 3 (“abc” repeated)
• "aaaa" has period 1 (“a” repeated)
• "abcde" has period 5 (itself)

def find_period(s):
    """Find the smallest period of string s using Z-function."""
    z = z_function(s)
    n = len(s)
    
    for p in range(1, n + 1):
        # Check if p is a valid period
        # s is a period p if n % p == 0 (or n - z[n-p] <= p for partial)
        # and Z[p] == n - p
        if p + z[p] == n and n % p == 0:
            return p
    
    return n  # The whole string is the period


print(find_period("abcabc"))     # 3
print(find_period("aaaa"))       # 1
print(find_period("abcde"))      # 5
print(find_period("abababab"))   # 2

All Periods of a String

def find_all_periods(s):
    """Find all periods of string s."""
    z = z_function(s)
    n = len(s)
    periods = []
    
    for p in range(1, n):
        # p is a period if s[p..n-1] is a prefix of s
        # i.e., Z[p] >= n - p
        if z[p] == n - p:
            periods.append(p)
    
    periods.append(n)  # The string itself is always a period
    return periods


print(find_all_periods("abcabc"))    # [3, 6]
print(find_all_periods("aaaa"))      # [1, 2, 4]
print(find_all_periods("ababab"))    # [2, 4, 6]

---

Application: Number of Distinct Substrings

Count the number of distinct substrings of a string. We add characters one at a time and count new substrings introduced:

def count_distinct_substrings(s):
    """
    Count distinct substrings by adding characters one at a time.
    After adding s[0..i], the new substrings are those ending at i
    that haven't appeared before.
    """
    n = len(s)
    count = 0
    
    for i in range(n):
        # Consider the string t = s[0..i] reversed
        # The number of new distinct substrings = (i+1) - max(Z values of reversed t)
        t = s[:i + 1][::-1]
        z = z_function(t)
        
        max_z = 0
        for j in range(1, len(z)):
            max_z = max(max_z, z[j])
        
        count += (i + 1) - max_z
    
    return count


print(count_distinct_substrings("abc"))    # 6: a, b, c, ab, bc, abc
print(count_distinct_substrings("aab"))    # 5: a, b, aa, ab, aab
print(count_distinct_substrings("abab"))   # 7: a, b, ab, ba, aba, bab, abab

---

Application: String Compression

Find the shortest representation of a string as repeated copies:

def compress_string(s):
    """Find shortest repeating unit and count of repetitions."""
    z = z_function(s)
    n = len(s)
    
    for p in range(1, n + 1):
        if n % p == 0:
            # Check if s is p repeated n/p times
            valid = True
            for i in range(p, n, p):
                if z[i] < min(p, n - i):
                    valid = False
                    break
            if valid:
                return s[:p], n // p
    
    return s, 1


print(compress_string("abcabcabc"))  # ('abc', 3)
print(compress_string("aaaa"))       # ('a', 4)
print(compress_string("abcd"))       # ('abcd', 1)
print(compress_string("ababab"))     # ('ab', 3)

---

Z-Algorithm vs KMP

Both Z-algorithm and KMP solve pattern matching in O(n + m) time. Here is how they compare:

Feature	Z-Algorithm	KMP
Array computed	Z-array (prefix match lengths)	Failure/pi array (longest proper prefix-suffix)
Conceptual clarity	More intuitive	More abstract
Pattern matching	Concatenate P$T, check Z[i]==m	Use failure function for transitions
Other applications	Periods, distinct substrings, compression	Automaton-based matching
Online matching	No (needs concatenation)	Yes (processes text character by character)
Implementation	Slightly simpler	Slightly more code

Relationship Between Z and KMP

The Z-array and KMP failure function encode the same information in different ways. You can convert between them in O(n):

def z_to_kmp(z):
    """Convert Z-array to KMP failure function."""
    n = len(z)
    pi = [0] * n
    
    for i in range(1, n):
        if z[i] > 0:
            for j in range(z[i] - 1, -1, -1):
                if pi[i + j] > 0:
                    break
                pi[i + j] = j + 1
    
    return pi

def kmp_to_z(pi):
    """Convert KMP failure function to Z-array."""
    n = len(pi)
    z = [0] * n
    z[0] = n
    
    for i in range(1, n):
        if pi[i] > 0:
            z[i - pi[i] + 1] = max(z[i - pi[i] + 1], pi[i])
    
    # Extend Z values
    for i in range(1, n):
        if z[i] > 0:
            for j in range(1, z[i]):
                if i + j < n:
                    z[i + j] = max(z[i + j], z[i] - j)
    
    return z

---

Complexity Analysis

Operation	Time	Space
Z-array construction	O(n)	O(n)
Pattern matching	O(n + m)	O(n + m)
Find period	O(n)	O(n)
All periods	O(n)	O(n)

The Z-algorithm is optimal for single pattern matching — you cannot do better than O(n + m) since you must read both the text and pattern.

---

Implementation Tips

Handling the Sentinel Character

The $ separator must not appear in either the pattern or text. Common choices:

• $ for lowercase-only strings
• \x00 (null byte) for general ASCII
• Use the length check instead: during Z-array computation on P$T, cap Z[i] at len(P).

def z_search_no_sentinel(text, pattern):
    """Pattern matching without using a sentinel character."""
    m = len(pattern)
    n = len(text)
    
    concat = pattern + text
    z = z_function(concat)
    
    results = []
    for i in range(m, len(concat)):
        # Z[i] might be > m because there's no separator,
        # but we only care if it's >= m
        if z[i] >= m:
            results.append(i - m)
    
    return results

---

Practice Problems

1. Find Pattern (Basic) — Direct Z-algorithm pattern matching.
2. Shortest Palindrome (LeetCode 214) — Reverse + concatenation + Z-algorithm.
3. Repeated Substring Pattern (LeetCode 459) — Check if the string has a period < n.
4. Longest Happy Prefix (LeetCode 1392) — Find the longest prefix that is also a suffix.
5. Number of Distinct Substrings — Add characters one by one, use Z to count new substrings.
6. String Period Queries — Precompute Z-array and answer period queries.

---

Key Takeaways

• The Z-array captures how much of each suffix matches the prefix of the string.
• The Z-box optimization ensures linear time by reusing previously computed information.
• Pattern matching works by concatenating P$T and checking where Z[i] == len(P).
• Z-algorithm is equivalent in power to KMP but often more intuitive to implement and understand.
• Beyond pattern matching, Z-arrays solve period detection, string compression, and substring counting problems.