Z Algorithm

Generated on 2025-07-10 02:08:46 Algorithm Cheatsheet for Technical Interviews

---

Z Algorithm Cheatsheet

1. Quick Overview

The Z Algorithm is a string searching algorithm used to find all occurrences of a pattern within a text. It computes the Z-array, where Z[i] is the length of the longest substring starting at index i which is also a prefix of the string.

When to Use:

• Finding all occurrences of a pattern in a text. Especially useful when you need to know the exact starting positions.
• String matching where pre-processing of the pattern is allowed and beneficial.
• Useful for problems involving finding repeated substrings or prefix-suffix relationships.

2. Time & Space Complexity

• Time Complexity: O(n), where n is the length of the string (pattern + separator + text). Linear time.
• Space Complexity: O(n), to store the Z-array. Linear space.

3. Implementation

Here are implementations in Python, Java, and C++:

Python:

def z_algorithm(s):
    """
    Computes the Z-array for a given string.

    Args:
        s: The input string.

    Returns:
        A list representing the Z-array.
    """
    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])  # Use previous information
        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

def find_pattern(text, pattern):
    """
    Finds all occurrences of a pattern in a text using the Z Algorithm.

    Args:
        text: The text string.
        pattern: The pattern string.

    Returns:
        A list of starting indices of the pattern in the text.
    """
    combined_string = pattern + "$" + text  # Separator to avoid pattern matching within itself
    z = z_algorithm(combined_string)
    n = len(pattern)
    occurrences = []
    for i in range(n + 1, len(combined_string)):
        if z[i] == n:
            occurrences.append(i - (n + 1))
    return occurrences


# Example Usage:
text = "ABABABABCABABAB"
pattern = "ABAB"
occurrences = find_pattern(text, pattern)
print(f"Occurrences of '{pattern}' in '{text}': {occurrences}") #Output: Occurrences of 'ABAB' in 'ABABABABCABABAB': [0, 2, 8, 10]

Java:

import java.util.ArrayList;
import java.util.List;

public class ZAlgorithm {

    public static int[] zAlgorithm(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    public static List<Integer> findPattern(String text, String pattern) {
        String combinedString = pattern + "$" + text;
        int[] z = zAlgorithm(combinedString);
        int n = pattern.length();
        List<Integer> occurrences = new ArrayList<>();
        for (int i = n + 1; i < combinedString.length(); i++) {
            if (z[i] == n) {
                occurrences.add(i - (n + 1));
            }
        }
        return occurrences;
    }

    public static void main(String[] args) {
        String text = "ABABABABCABABAB";
        String pattern = "ABAB";
        List<Integer> occurrences = findPattern(text, pattern);
        System.out.println("Occurrences of '" + pattern + "' in '" + text + "': " + occurrences); //Output: Occurrences of 'ABAB' in 'ABABABABCABABAB': [0, 2, 8, 10]
    }
}

C++:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> zAlgorithm(string s) {
    int n = s.length();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

vector<int> findPattern(string text, string pattern) {
    string combinedString = pattern + "$" + text;
    vector<int> z = zAlgorithm(combinedString);
    int n = pattern.length();
    vector<int> occurrences;
    for (int i = n + 1; i < combinedString.length(); i++) {
        if (z[i] == n) {
            occurrences.push_back(i - (n + 1));
        }
    }
    return occurrences;
}

int main() {
    string text = "ABABABABCABABAB";
    string pattern = "ABAB";
    vector<int> occurrences = findPattern(text, pattern);
    cout << "Occurrences of '" << pattern << "' in '" << text << "': ";
    for (int i = 0; i < occurrences.size(); i++) {
        cout << occurrences[i] << (i == occurrences.size() - 1 ? "" : ", ");
    }
    cout << endl; //Output: Occurrences of 'ABAB' in 'ABABABABCABABAB': 0, 2, 8, 10
    return 0;
}

4. Common Patterns

• Exact String Matching: The primary use case, as demonstrated above.
• Finding the longest prefix that is also a suffix: Calculate the Z-array of the string. The largest value in the Z-array represents the length of the longest prefix that is also a suffix.
• Substring Matching with Wildcards: While not directly applicable, the Z-Algorithm can be adapted with preprocessing or modifications to handle wildcard characters. This might involve replacing wildcards with a special character and adjusting the matching logic.
• Pattern Searching in Data Streams: The Z-Algorithm can be adapted for streaming scenarios. You can process the text in chunks, maintaining the Z-array for the current chunk and updating it as new data arrives.

5. Pro Tips

• Separator Choice: The separator character (e.g., $) must not be present in either the pattern or the text. Otherwise, it will lead to incorrect matches.
• Optimization: The key optimization lies in reusing previously computed Z-values. The if (i <= r) condition and z[i] = min(r - i + 1, z[i - l]); line are crucial for achieving linear time complexity.
• Boundary Cases: Carefully handle edge cases where the pattern is longer than the text or when the pattern is empty. The provided code handles these cases gracefully but always double-check.
• Memory Usage: For extremely large texts, consider processing the text in chunks to reduce memory consumption. However, this may increase the overall time complexity.
• Understanding l and r: l and r define the rightmost interval [l, r] such that s[l...r] is a prefix of s. Maintaining this interval correctly is crucial for the algorithm’s efficiency.

6. Practice Problems

1. LeetCode 28. Find the Index of the First Occurrence in a String: (Implement strStr()). Solve using the Z Algorithm.
2. Longest Prefix Suffix: Given a string, find the length of the longest proper prefix which is also a proper suffix. (Hint: Use Z Algorithm).
3. String Compression: Given a string, compress it by replacing repeated substrings with their count. (e.g., “ABABABAB” becomes “4(AB)”). The Z-Algorithm can help identify repeating substrings. (This problem is more advanced and requires combining the Z algorithm with other techniques).

7. Templates

Here are reusable code templates for the Z algorithm in C++, Python, and Java. These are bare-bones implementations of the Z-algorithm calculation itself, ready to be plugged into your problem-solving code.

C++ Template:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> zAlgorithm(const string& s) {
    int n = s.length();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

// Example usage (add your problem-specific logic here)
int main() {
    string s = "ABABCABAB";
    vector<int> z = zAlgorithm(s);

    cout << "Z-Array for '" << s << "': ";
    for (int val : z) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Python Template:

def z_algorithm(s):
    """
    Calculates the Z-array for a given string.
    """
    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 = i
            r = i + z[i] - 1
    return z

# Example usage (add your problem-specific logic here)
if __name__ == "__main__":
    s = "ABABCABAB"
    z = z_algorithm(s)
    print(f"Z-Array for '{s}': {z}")

Java Template:

import java.util.Arrays;

public class ZAlgorithmTemplate {

    public static int[] zAlgorithm(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    // Example usage (add your problem-specific logic here)
    public static void main(String[] args) {
        String s = "ABABCABAB";
        int[] z = zAlgorithm(s);
        System.out.println("Z-Array for '" + s + "': " + Arrays.toString(z));
    }
}

This comprehensive cheatsheet should provide a solid foundation for understanding and applying the Z Algorithm in various coding scenarios. Remember to practice and experiment to solidify your understanding.