Z-Algorithm in Data Structures - CSU083 | Shoolini University

Z-Algorithm for Pattern Searching

2025, February 10

1. Prerequisites

Before understanding the Z-Algorithm, you must be familiar with the following foundational concepts:

2. What is the Z-Algorithm?

The Z-Algorithm is an efficient string matching algorithm that preprocesses a string to find occurrences of a pattern in a text. It constructs a Z-array, where each element at index i represents the length of the longest substring starting from i that matches the prefix of the string.

It works in O(n) time complexity, making it one of the fastest algorithms for substring search.

3. Why does this algorithm exist?

The Z-Algorithm exists to provide an efficient way to solve string pattern matching problems. Traditional approaches, such as the naive search algorithm, have a time complexity of O(nm) (where n is the length of the text and m is the length of the pattern), which is inefficient for large inputs.

Some real-world applications include:

4. When should you use the Z-Algorithm?

The Z-Algorithm is useful when:

5. How does it compare to alternatives?

5.1 Strengths

5.2 Weaknesses

5.3 Comparison with Other Algorithms

"
Algorithm Time Complexity Best Use Case Drawback
Z-Algorithm O(n) Exact pattern matching, longest prefix problems Requires preprocessing
KMP (Knuth-Morris-Pratt) O(n) Single pattern search with efficient preprocessing Requires an additional LPS array
Rabin-Karp O(n) (on average), O(nm) (worst case) Multiple pattern matching with hashing Collisions in hashing can degrade performance
Boyer-Moore O(n/m) (best case), O(nm) (worst case) Search large texts efficiently Complex preprocessing

6. Basic Implementation

6.1 Python Implementation of the Z-Algorithm

The following is a Python implementation of the Z-Algorithm:

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    l, r = 0, 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

# Example usage:
text = "abacabacab"
pattern = "abac"
concat = pattern + "$" + text  # Using a separator character '$'
z_values = z_algorithm(concat)

# Extracting pattern occurrences
pattern_length = len(pattern)
matches = [i - pattern_length - 1 for i in range(len(z_values)) if z_values[i] == pattern_length]

print("Z-Array:", z_values)
print("Pattern found at indices:", matches)

7. Dry Run: Step-by-Step Execution

We will dry run the algorithm with the input:

7.1 Step-by-Step Execution

"
Index (i) Substring Compared Z[i] l (Left) r (Right) Explanation
0 "a" 0 0 0 Z[0] is always 0.
1 "b" 0 1 0 No prefix match found.
2 "a" 1 2 2 Matches prefix "a".
3 "c" 0 2 2 No further match.
4 "$" 0 4 4 Separator encountered.
5 "a" 4 5 8 Matches full pattern "abac".
9 "a" 4 9 12 Another match of "abac".

7.2 Output Interpretation

The Z-array generated: [0, 0, 1, 0, 0, 4, 0, 1, 0, 4, 0, 1, 0]

The pattern "abac" occurs at indices [0, 4] in the given text.

8. Time & Space Complexity Analysis

8.1 Worst-Case Time Complexity

The Z-Algorithm processes each character at most twice—once in the main loop and once in the inner loop that extends matches. Thus, the worst-case time complexity is:

O(n), where n is the length of the input string.

8.2 Best-Case Time Complexity

If the pattern has no repeated substrings and mismatches occur early, the algorithm does minimal processing, leading to a best-case time complexity of:

O(n) (still linear but with fewer operations).

8.3 Average-Case Time Complexity

On average, the Z-Algorithm maintains a linear runtime because it efficiently skips over sections where it already has computed values. The average complexity remains:

O(n).

9. Space Complexity Analysis

The Z-Algorithm stores the Z-array of size n, where n is the length of the string. Thus, its space complexity is:

O(n).

9.1 Impact of Input Size on Space

10. Trade-offs of the Z-Algorithm

10.1 Strengths

10.2 Weaknesses

10.3 When to Choose Z-Algorithm?

11. Optimizations & Variants

11.1 Common Optimizations

Several optimizations can improve the Z-Algorithm’s efficiency in real-world scenarios:

11.2 Variants of the Z-Algorithm

Several modifications exist to tailor the Z-Algorithm for different applications:

12. Comparing Iterative vs. Recursive Implementations

12.1 Iterative Implementation

The iterative version is the most common and efficient. It processes the string in a single loop using two pointers (l, r) to optimize lookups.

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    l, r = 0, 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

12.2 Recursive Implementation

A recursive version follows a divide-and-conquer approach. It reduces problem size by computing smaller Z-values and propagating results.

def z_recursive(s, Z=None, l=0, r=0, i=1):
    if Z is None:
        Z = [0] * len(s)

    if i >= len(s):
        return Z

    if i <= r:
        Z[i] = min(r - i + 1, Z[i - l])

    while i + Z[i] < len(s) 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_recursive(s, Z, l, r, i + 1)

12.3 Efficiency Comparison

"
Aspect Iterative Implementation Recursive Implementation
Time Complexity O(n) O(n) (but may suffer from recursion overhead)
Space Complexity O(n) (for Z-array) O(n) (for Z-array + recursion stack)
Performance Faster in practice Slower due to recursive call overhead
Ease of Understanding More intuitive Conceptually clear but harder to debug

12.4 Conclusion

13. Edge Cases & Failure Handling

13.1 Common Pitfalls & Edge Cases

When implementing the Z-Algorithm, certain edge cases can lead to incorrect behavior or inefficiency:

14. Test Cases to Verify Correctness

14.1 Basic Test Cases

Below are essential test cases to validate the correctness of the Z-Algorithm:

def run_tests():
    test_cases = [
        ("aaaaa", "aa", [0, 1, 2, 3]),  # Repeated characters
        ("abcdef", "xyz", []),  # Pattern not in text
        ("abacabacab", "abac", [0, 4]),  # Multiple matches
        ("a", "a", [0]),  # Single character match
        ("abacabadabacaba", "abacab", [0, 8]),  # Overlapping patterns
        ("", "a", []),  # Empty text
        ("a", "", []),  # Empty pattern
        ("abcde", "abcde", [0])  # Exact match
    ]

    for text, pattern, expected in test_cases:
        concat = pattern + "$" + text
        z_values = z_algorithm(concat)
        pattern_length = len(pattern)
        result = [i - pattern_length - 1 for i in range(len(z_values)) if z_values[i] == pattern_length]

        assert result == expected, f"Failed for {text}, {pattern}, got {result}"

    print("All test cases passed!")

# Run the test suite
run_tests()

14.2 Explanation of Expected Outputs

15. Real-World Failure Scenarios

15.1 Memory Exhaustion

Problem: Processing extremely large strings in memory-constrained environments can lead to memory errors.

Solution: Implement chunk-based processing or use streaming Z-Algorithm variants.

15.2 Handling Unicode & Special Characters

Problem: Some implementations may fail on Unicode text like `"你好你好"`.

Solution: Ensure encoding compatibility and proper character comparisons.

15.3 Incomplete Input Processing

Problem: Incorrect `Z[i]` updates when `l` and `r` pointers are not properly maintained.

Solution: Ensure `l` and `r` values update correctly after each match.

15.4 Overlapping Patterns

Problem: The algorithm may not correctly identify overlapping substrings.

Solution: Modify logic to account for overlapping cases explicitly if required.

15.5 Edge Cases in Real-World Applications

16. Real-World Applications & Industry Use Cases

The Z-Algorithm is widely used across multiple domains where efficient substring searching is critical.

16.1 Common Applications

16.2 Industry Use Cases

17. Open-Source Implementations

Many open-source libraries provide Z-Algorithm implementations:

18. Practical Project: String Pattern Finder

This script uses the Z-Algorithm to find occurrences of a pattern in large text files, useful for log analysis or plagiarism detection.

import sys

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    l, r = 0, 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

def find_pattern(text, pattern):
    concat = pattern + "$" + text
    z_values = z_algorithm(concat)
    pattern_length = len(pattern)

    matches = [i - pattern_length - 1 for i in range(len(z_values)) if z_values[i] == pattern_length]

    return matches

if __name__ == "__main__":
    if len(sys.argv) != 3:
        print("Usage: python pattern_finder.py  ")
        sys.exit(1)

    file_path = sys.argv[1]
    pattern = sys.argv[2]

    with open(file_path, "r", encoding="utf-8") as file:
        text = file.read()

    occurrences = find_pattern(text, pattern)

    if occurrences:
        print(f"Pattern found at indices: {occurrences}")
    else:
        print("Pattern not found.")

18.1 How It Works

18.2 Example Usage

python pattern_finder.py large_text.txt "error"

This will search for the word "error" in large_text.txt and return all its occurrences.

18.3 Real-World Utility

19. Competitive Programming & System Design Integration

19.1 Competitive Programming Use Cases

The Z-Algorithm is widely used in competitive programming for fast pattern matching. Some common scenarios include:

19.2 System Design Use Cases

The Z-Algorithm is useful in large-scale systems requiring efficient text processing:

20. Assignments for Mastery

20.1 Solve at Least 10 Problems Using the Z-Algorithm

Practice solving these problems on competitive programming platforms:

  1. Find Pattern in Text: Given a string and a pattern, return all starting indices of the pattern in the text.
  2. Longest Prefix Repeated in String: Compute the longest prefix that is also found elsewhere in the string.
  3. Smallest Period of a String: Find the smallest repeating unit in a given string.
  4. DNA Sequence Matching: Find occurrences of a DNA sequence in a genome string.
  5. Palindrome Substring Detection: Check if any prefix of a string forms a palindrome.
  6. Spam Keyword Detection: Given a chat message, detect banned words efficiently.
  7. Repeated Substring Pattern: Determine if a string is a repetition of one of its substrings.
  8. Count Distinct Substrings: Use Z-values to compute the number of distinct substrings in a string.
  9. Suffix Matching: Given a query, find if it matches any suffix of a given word.
  10. Longest Common Prefix between Two Strings: Find the longest prefix shared by two given strings.

20.2 Use the Z-Algorithm in a System Design Problem

Design a text-based search engine with Z-Algorithm integration:

20.3 Practice Implementing Under Time Constraints

To improve speed, practice implementing the Z-Algorithm within: