Z-Function (Z-Algorithm)

Share

Compute Z-array where Z[i] = length of longest substring starting at i that is also a prefix of s. Use for pattern matching.

Example 1
Input: s="aabxaa" → Output: Z=[6,1,0,0,2,1]
Example 2
Input: pattern="abc" in text="aabcabcabc" → Output: Indices: [1,4,7]

Solution Approach

Build Z-array in O(n) using window [l,r]. Shift window right when Z value is computed.

  • Initialize z[0]=n, l=0, r=0
  • For i from 1 to n-1: if i < r use z[i-l] as start
  • Expand: while i+z[i] < n and s[z[i]]==s[i+z[i]], z[i]++
  • Update l,r if i+z[i]-1 > r
  • For pattern matching: check z values == pattern.length()
Java
public int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = Math.min(r - i, z[i - l]);
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}
// Pattern matching using Z-function
public List<Integer> search(String text, String pattern) {
    String combined = pattern + "$" + text;
    int[] z = zFunction(combined);
    List<Integer> result = new ArrayList<>();
    int m = pattern.length();
    for (int i = m + 1; i < combined.length(); i++)
        if (z[i] == m) result.add(i - m - 1);
    return result;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)