Lesson 35.2 · Advanced String Algorithms

The Z-Function

z[i] is the length of the longest substring starting at i that matches a prefix of the string. Searching for p in t becomes computing Z of p + '$' + t.

12 min

Think of it like this

Holding a ruler with the start of a word printed on it and sliding it along the same word: at each position you note how many letters line up before the first difference.

1.The Z-box trick

Keep the rightmost window [l, r) that matches a prefix. For i inside it, z[i] is at least min(r − i, z[i − l]) because that part mirrors an earlier position; then extend by direct comparison. Each extension moves r right, so the whole array takes O(n).

Pattern search: compute Z of p + "$" + t; every position with z = |p| is a match. Z is often simpler to reason about than lps, and the two carry the same information.

Main.java

import java.util.Arrays;

public class Main {
    static int[] z(String s) {
        int n = s.length();
        int[] z = new int[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;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(z("aabxaab")));
    }
}

Output

[0, 1, 0, 0, 3, 1, 0]

Remember

z[i] = match length with the prefix.
Reuse the [l, r) box.
Search with p + separator + t.

Common mistakes

Choosing a separator character that can appear in the strings.

Command Palette

The Z-Function

1.The Z-box trick