Z-Algorithm for Pattern Matching

Problem

The Z-Algorithm builds a Z-array where Z[i] is the length of the longest substring starting at i that matches a prefix of the string. It is used for pattern matching by searching "pattern$text".

Input:  s = "aabxaabxcaabxaabxay"
Z array (partial): Z[4] = 5 (matches prefix "aabxa")

Python Solution

def z_array(s):
    n = len(s)
    z = [0] * n
    left = right = 0
    for i in range(1, n):
        if i < right:
            z[i] = min(right - i, z[i - left])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z

def z_search(text, pattern):
    combined = pattern + "$" + text
    z = z_array(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(len(z)) if z[i] == m]

C++ Solution

vector<int> zArray(string s) {
    int n = s.size();
    vector<int> z(n, 0);
    int left = 0, right = 0;
    for (int i = 1; i < n; i++) {
        if (i < right) z[i] = min(right - i, z[i - left]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > right) { left = i; right = i + z[i]; }
    }
    return z;
}

vector<int> zSearch(string text, string pattern) {
    string combined = pattern + "$" + text;
    vector<int> z = zArray(combined);
    int m = pattern.size();
    vector<int> result;
    for (int i = 0; i < z.size(); i++) {
        if (z[i] == m) result.push_back(i - m - 1);
    }
    return result;
}

Java Solution

class Solution {
    public int[] zArray(String s) {
        int n = s.length();
        int[] z = new int[n];
        int left = 0, right = 0;
        for (int i = 1; i < n; i++) {
            if (i < right) z[i] = Math.min(right - i, z[i - left]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (i + z[i] > right) { left = i; right = i + z[i]; }
        }
        return z;
    }

    public List<Integer> zSearch(String text, String pattern) {
        String combined = pattern + "$" + text;
        int[] z = zArray(combined);
        int m = pattern.length();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < z.length; i++) {
            if (z[i] == m) result.add(i - m - 1);
        }
        return result;
    }
}

Complexity

Time: O(n + m) — the Z-array is built in linear time by reusing the [left, right) match window instead of recomputing matches from scratch at every index. Space: O(n + m) for the combined string and its Z-array.