☕ DSA Java Articles

Topics › Strings › Hard String Problems

Z function

Hard TUF ID 981 A2ZSDE

Java source ↗ Edit this article ↗

Problem

For a string s of length n, the Z-array is defined by: z[i] is the length of the longest substring starting at position i that is also a prefix of s. By convention z[0] = 0 (the whole string trivially matches itself, which carries no information).

The task has two parts, and the second is the usual reason for the first:

  1. Compute the Z-array of a string.
  2. Given text and pattern, return every 0-based index where pattern occurs in text, overlaps included, using the Z-array.

Constraints: 0 ≤ n ≤ 10^5. For the search, an empty pattern or one longer than the text gives an empty list.

Example 1

s = "aabxaab"
z = [0, 1, 0, 0, 3, 1, 0]
// z[1] = 1: "a" matches the prefix, "ab" does not
// z[4] = 3: "aab" matches the prefix "aab", then the string ends

Example 2

s = "aaaaa"
z = [0, 4, 3, 2, 1]       // from position i, the rest of the string is all a's

Example 3

text = "abracadabra", pattern = "abra"
answer = [0, 7]

Glue the pattern in front of the text: s = pattern + text, with m = |pattern|. A position i ≥ m of s lies in the text part, at text index i - m. If z[i] ≥ m, then the m characters starting at i equal the first m characters of s, which are the pattern. So the pattern occurs at text index i - m. Conversely, every occurrence produces such a z[i]. Pattern search therefore costs exactly one Z-array computation plus a scan.

Most write-ups insert a separator such as $ between pattern and text, which caps every z[i] at m and lets you test z[i] == m. The test z[i] ≥ m works without a separator, and so it works for any alphabet, including strings that might contain $.

Approach 1: Brute force

Intuition. Follow the definition. For each position i, compare s[i], s[i+1], ... against s[0], s[1], ... and stop at the first mismatch or at the end of the string. For the search, the matching brute force is to compare the pattern against every window of the text directly.

Algorithm (Z-array).

  1. For each i from 1 to n - 1, start with z[i] = 0.
  2. While i + z[i] < n and s[z[i]] == s[i + z[i]], increment z[i].
static int[] zBrute(String s) {
    int n = s.length();
    int[] z = new int[n];
    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
    }
    return z;
}

static List<Integer> searchBrute(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    if (m == 0) return res;
    for (int i = 0; i + m <= n; i++) {
        if (text.regionMatches(i, pattern, 0, m)) res.add(i);
    }
    return res;
}

Complexity. Time O(n^2) for the Z-array: on "aaaa...a" position i extends n - i steps, which sums to about n^2 / 2. The search is O(n · m). Space O(n) for the array, O(1) extra for the search.

Approach 2: Optimal, the Z-box

Intuition. The brute force forgets what it has learned. Suppose that while processing earlier positions we found a segment s[l..r) that equals the prefix s[0..r-l). Call it the Z-box, and keep the one reaching furthest right. Now take a position i inside the box (l < i < r). Because the box is a copy of the prefix, the characters s[i..r) are the same as s[i-l..r-l), and we already know how far a match from i - l reaches: z[i - l]. So, for free:

Both cases are captured by starting at z[i] = min(r - i, z[i - l]) and then running the same extension loop as the brute force. If the match from i ends beyond r, it becomes the new Z-box.

Algorithm.

  1. Set l = r = 0.
  2. For i = 1 .. n - 1:
    • If i < r, set z[i] = min(r - i, z[i - l]).
    • Extend while s[z[i]] == s[i + z[i]].
    • If i + z[i] > r, set l = i, r = i + z[i].
  3. For the search, compute the Z-array of pattern + text and collect every i ≥ m with z[i] ≥ m, reporting i - m.
static int[] zOptimal(String s) {
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;                                  // s[l..r) equals s[0..r-l), with r as large as possible
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = Math.min(r - i, z[i - l]);   // copy the answer from inside the prefix
        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;
}

static List<Integer> searchZ(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int m = pattern.length();
    if (m == 0 || m > text.length()) return res;
    int[] z = zOptimal(pattern + text);
    for (int i = m; i < z.length; i++) {
        if (z[i] >= m) res.add(i - m);                 // the next m characters equal the pattern
    }
    return res;
}

Dry run on s = "aabxaab":

i inside box? starting z[i] after extending box [l, r)
1 no 0 1 [1, 2)
2 no 0 0 [1, 2)
3 no 0 0 [1, 2)
4 no 0 3 [4, 7)
5 yes: min(7 - 5, z[1] = 1) 1 1 [4, 7)
6 yes: min(7 - 6, z[2] = 0) 0 0 [4, 7)

Positions 5 and 6 reused earlier answers: each needed a single failed comparison.

Complexity. Time O(n). Every comparison in the extension loop either fails, which happens at most once per i, or succeeds. A successful comparison always examines a character at or beyond r, and afterwards r is moved past it. Since r never decreases and never exceeds n, there are at most n successes in total. The search is O(n + m). Space O(n + m) for the concatenated string and its Z-array.

Edge cases and pitfalls