Compute Z-array where Z[i] = length of longest substring starting at i that is also a prefix of s. Use for pattern matching.
Input: s="aabxaa" → Output: Z=[6,1,0,0,2,1]
Input: pattern="abc" in text="aabcabcabc" → Output: Indices: [1,4,7]
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()
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)