Z-function

Why this matters when you build with AI

An AI tool asked for a substring search often gives one of three answers: a call to the language's find function, a hash map of all substrings, or a double loop. The first two can be fast, and the third is simple to read. None of them tells you the running time for your input size unless you ask. A common claim is "this is linear time", and it is often false for a loop with a hidden inner search.

The Z-function is a second linear-time tool that solves the same kind of problem as the prefix function from the previous lesson. Knowing both lets you pick the one that matches the question. This lesson builds the Z-function, proves its running time, and compares it with the prefix function.

Checking an AI answer takes two steps. Read the loop and mark the pointers that only move in one direction, which is the reason the total work is small. Then run the code and a brute force program on random small strings, and compare the outputs. The brute force program tries every position with no clever idea, so it is easy to trust.

Terms used in this lesson

A string s has length n, indexed from 0. The longest common prefix (LCP) of two strings is the longest length for which their first characters agree. The LCP of abacaba and acaba is 1, because a matches and then b and c differ.

The Z-array of s is the list z where z[i] is the LCP of s and the suffix that starts at i. By convention z[0] is n, the length of the whole string, because the whole string matches itself.

The Z-box is the window [l, r) of positions already known to match. It means the characters s[l..r) equal s[0..r-l). Here [l, r) includes l and excludes r, the same as a loop range in C++.

A pattern is the string you search for, and a text is the string you search in. An occurrence is a start position where the pattern matches.

The idea: the Z-array with an example

Take s = abacaba. Here is the Z-array, one row per index.

The array is 7 0 1 0 3 0 1, and that is the output of the program in the code section below.

Look at index 4. The suffix aba equals the prefix aba, so z[4] is 3. This is the key fact: a Z-value of k at index i says that s[i..i+k) equals s[0..k). Every Z-value tells you where a copy of the start of the string appears.

Computing the Z-array in linear time

A naive method compares each suffix with the prefix from the beginning. That costs up to n times n. The window trick reuses earlier comparisons.

Keep the Z-box [l, r) with the largest r found so far. Suppose the current index i lies inside the box, so i < r. The characters s[i..r) are a copy of s[i-l..r-l), because the box says s[l..r) equals s[0..r-l). The copy at i-l is a Z-value that was already computed, so z[i] is at least min(r - i, z[i - l]). Only the part beyond r has to be compared character by character.

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    if (n == 0) return z;
    z[0] = n;
    int l = 0, r = 0;  // the window [l, r): s[l..r) == s[0..r-l)
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

Trace the window on aabxaab, which is a string of length 7. Each row is the state after processing index i.

At index 5 the copy z[1] is 1, which is smaller than r - i = 2, so the code does not compare any new characters beyond that copy except one check that fails. The result matches the output 7 1 0 0 3 1 0.

Why the total work is O(n)

Each character comparison in the while loop either succeeds or stops the loop for this index. A successful comparison moves i + z[i] forward by one, and the box end r only moves to the right. So the total number of successful comparisons is at most n, because r can move at most n times. Each index also has at most one failed comparison, which is at most n more. The total is O(n).

Relation to the prefix function

The prefix function from the previous lesson and the Z-array both have n entries and both are linear to build. They answer different questions about the same string.

• pi[i] is the longest border of the prefix that ends at i. It looks left from i, at how the prefix ends.
• z[i] is the LCP of the whole string and the suffix that starts at i. It looks right from i, at how the suffix begins.

When a task asks for borders, the number of times a prefix repeats, or a machine that reads text one letter at a time, the prefix function is the natural tool. When a task asks where the start of the string appears in the rest of the string, or how far each suffix agrees with the start, the Z-array is the direct answer. Either array can be converted into the other in linear time, so the choice is about which question the task asks.

The conversion from a Z-array to a prefix function is below. The code is short, but it depends on a subtle fact that I checked by testing rather than by a proof.

vector<int> z_to_prefix(const vector<int>& z) {
    int n = z.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        for (int j = z[i] - 1; j >= 0; j--) {
            if (pi[i + j] > 0) break;
            pi[i + j] = j + 1;
        }
    }
    return pi;
}

The idea is that z[i] = k says the suffix at i matches the prefix for k characters, so the prefix ending at i + j has a border of length j + 1 starting at i. The loop fills each position once, and each inner step either fills a new position or ends the loop, so the total work is O(n). I tested this function against a brute force prefix function on 600 random strings of length 1 to 14, with no differences. I did not prove that the break never skips a needed value, so if you depend on this conversion, test it on your own data first.

The conversion gives the same answer as the program in the prefix-function lesson. On aabaaab, the Z-array is 7 1 0 2 3 1 0, and the converted prefix function is 0 1 0 1 2 2 3, the same as the direct computation.

Worked problem: how often each prefix occurs

Here is an original problem to solve on paper first.

A string s of lowercase letters is given. For each length k from 1 to n, count the positions i with 0 <= i <= n - k such that the substring s[i..i+k) equals the prefix s[0..k). Print the n counts on one line, separated by spaces.

Input: one line with the string s. Limits: 1 <= n <= 300000. Output: n integers, the count for k = 1, 2, ..., n.

Example: for aabxaab, the output is 4 2 2 1 1 1 1.

A brute force solution compares every position with every length, which is too slow at n = 300000. The Z-array gives a linear method. Position i matches the prefix of length k exactly when z[i] >= k, because z[i] is the longest match. So each position i contributes one to every k from 1 up to z[i]. Adding one to a whole range of k values is a job for a difference array: add one at the start of the range, subtract one just after its end, then take running sums.

For aabxaab, the Z-array is 7 1 0 0 3 1 0. Position 0 contributes to k = 1 through 7. Position 1 contributes to k = 1. Position 4 contributes to k = 1 through 3. Position 5 contributes to k = 1. The counts for k = 1 are the positions 0, 1, 4 and 5, which is 4. For k = 2 the positions are 0 and 4, which is 2. For k = 3 they are again 0 and 4, which is 2. For k = 4 only position 0 remains, which is 1. These match the output 4 2 2 1 1 1 1.

Here is the complete program. It also contains the pattern search from the next section.

#include <bits/stdc++.h>
using namespace std;
 
// z[i] = length of the longest common prefix of s and s[i..]; z[0] = n.
vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    if (n == 0) return z;
    z[0] = n;
    int l = 0, r = 0;  // the window [l, r): s[l..r) == s[0..r-l)
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}
 
// Start positions of p in t, overlaps included.
vector<int> find_all(const string& p, const string& t) {
    int m = p.size();
    string s = p + '#' + t;  // '#' must not appear in p or t
    vector<int> z = z_function(s);
    vector<int> res;
    for (int i = m + 1; i < (int)s.size(); i++)
        if (z[i] >= m) res.push_back(i - m - 1);
    return res;
}
 
// For each k = 1..n, how many i in [0, n) have s[i..i+k) == s[0..k).
vector<long long> prefix_popularity(const string& s) {
    int n = s.size();
    vector<int> z = z_function(s);
    vector<long long> diff(n + 2, 0);
    for (int i = 0; i < n; i++) {
        if (z[i] >= 1) {  // position i matches every prefix of length 1..z[i]
            diff[1] += 1;
            diff[z[i] + 1] -= 1;
        }
    }
    vector<long long> res;
    long long run = 0;
    for (int k = 1; k <= n; k++) {
        run += diff[k];
        res.push_back(run);
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string task;
    cin >> task;
    if (task == "find") {
        string p, t;
        cin >> p >> t;
        vector<int> r = find_all(p, t);
        cout << r.size() << "\n";
        for (size_t i = 0; i < r.size(); i++) cout << r[i] << (i + 1 < r.size() ? " " : "\n");
        if (r.empty()) cout << "\n";
    } else if (task == "pop") {
        string s;
        cin >> s;
        vector<long long> c = prefix_popularity(s);
        for (size_t i = 0; i < c.size(); i++) cout << c[i] << (i + 1 < c.size() ? " " : "\n");
    } else {
        string s;
        cin >> s;
        vector<int> z = z_function(s);
        for (size_t i = 0; i < z.size(); i++) cout << z[i] << (i + 1 < z.size() ? " " : "\n");
    }
}

Compile with g++ -std=c++17 -O2 -o zfun zfun.cpp (g++ 15.2.0 was used for the tests in this lesson). Run the example:

$ printf 'pop\naabxaab\n' | ./zfun
4 2 2 1 1 1 1

The program output for the Z-array of the same string is 7 1 0 0 3 1 0, which agrees with the trace above.

I tested prefix_popularity against a brute force that loops over every k and every start position. The test used 500 random strings of length 1 to 14, half over a and b and half over a, b and c, with no differences. find_all was tested the same way with patterns of length 1 to 4 and texts of length 0 to 14, also with no differences. The random generator and the brute force are not part of this lesson's code.

Pattern search with the Z-array

To find a pattern p in a text t, build p + '#' + t and compute its Z-array. The separator # must not appear in p or t. Every position i in the text part gives z[i], the length of the match between the combined string and its own start. The pattern occurs at text position i - m - 1 exactly when z[i] >= m, where m is the length of p.

The separator stops a match from running past the end of the pattern. Since the start of the combined string is p followed by #, the value z[i] in the text part can never be more than m. That is why the test can be written as z[i] == m if you prefer, and it gives the same answer as >=. Without the separator, the value can be longer than m, and the equality test gives wrong answers. The output below shows this.

$ printf 'find\naab\naabxaabaab\n' | ./zfun
3
0 4 7

When I ran the same pattern search without the separator and with an equality test, the pattern aa in the text aaa gave only the start 1, when the correct starts are 0 and 1. The check z[2] was 3, which is not equal to 2, so position 0 was dropped. This is a real symptom of a missing separator.

Complexity

The Z-array takes O(n) time and O(n) memory. Pattern search takes O(|p| + |t|) time, and prefix popularity takes O(n) time after the Z-array. These bounds are worst-case for the window method, since the argument above does not depend on the input. The constant factor is small, but a judge may still time out on a bad implementation, so measure on a large random input when the limits are tight.

Common mistakes

1. Forgetting z[0] = n. The whole string matches itself. Leaving z[0] at 0 drops that match from prefix popularity. On aabxaab the program prints 3 1 1 0 0 0 0 instead of 4 2 2 1 1 1 1, because position 0 no longer contributes to any k.

2. Dropping the cap min(r - i, z[i - l]). Without the cap, a value copied from z[i-l] can run past the end of the box, and the code then reports matches that were never checked. On aaaab the correct Z-array is 5 3 2 1 0. The version without the cap printed 5 3 3 3 3.

3. Equality test without a separator. As shown above, aa in aaa gives the wrong starts when the separator is missing and the test is == m. Keep the separator, or use >= m and accept that the separator is only a guard.

4. Counting i = 0 as a border. The test z[i] == n - i is true for i = 0, because z[0] = n. A border must be proper. For abacaba, counting from i = 0 gives 3, but the proper borders are a and aba, so the answer is 2. Start the count at i = 1.

5. Off-by-one in the while condition. The check i + z[i] < n must come before reading s[i + z[i]]. Writing <= n reads one character past the end of the string, which is undefined behaviour in C++. The symptom depends on the compiler and the input.

Hands-on exercise

Work in a new folder on your machine.

1. Save the complete program as zfun.cpp and compile it with g++ -std=c++17 -O2 -o zfun zfun.cpp.
2. Write brute.py that reads the same input and prints the Z-array by comparing each suffix with the whole string character by character.
3. Write gen.py that prints a random string of letters a and b, with length from 1 to 20.
4. Run both programs on 300 random inputs. For zfun, give the input as two lines: the word z, then the string. Compare the output lines. Report the first input that differs, if any.
5. Remove the min cap from z_function in a copy of the file, run the same comparison, and count how many inputs fail. Explain in one sentence why the failures appear.

A good result is that step 4 has no differences, and step 5 has failures that you can explain. If step 4 shows a difference, print that input, compute the Z-array by hand with the table in this lesson, and find which of the two outputs is right.

Prompt for checking an AI answer

Use this prompt when an AI tool writes a substring or pattern function that it says is linear.

Here is my function that counts how many times each prefix of s occurs in s.
1. For the Z-array of s, explain why each position contributes to a range of k values, and what range that is.
2. Give the smallest string where removing the line z[0] = n changes the output, and show both outputs.
3. Explain why the total number of window moves is at most n, and say which pointer never moves left.
Do not rewrite the code. Only report errors and their smallest inputs.

A good answer says the range is 1 to z[i], shows a string such as aa where z[0] changes the count for k = 1 and 2, and names the right end r of the window as the pointer that never moves left. An answer that claims linear time without naming the pointer is not enough.

Checklist

• Set z[0] = n before the main loop.
• Use min(r - i, z[i - l]) only when i < r.
• Check i + z[i] < n before reading s[i + z[i]].
• Start border counts at i = 1, because a border must be proper.
• Keep a separator between pattern and text when you use the Z-array for matching.
• Test the function against a brute force on at least a few hundred small random strings.

Summary

The Z-array gives, for every position, the length of the match between the whole string and the suffix that starts there. A window that remembers the rightmost match lets each position reuse earlier comparisons, so the array is built in linear time. The same array answers pattern search and prefix popularity, and it converts into the prefix function when a task asks about borders.

Practice problems

Practice 1: Suffixes that are also prefixes

Given a string s of lowercase letters, count the proper borders of s by counting the positions i from 1 to n - 1 where the suffix starting at i equals the prefix of the same length. Print the count.

Show the answer

Hint: a suffix starting at i equals the prefix of its length exactly when z[i] == n - i. Count those positions with i from 1 upward, so that z[0] is not counted. On abacaba the positions are 4 and 6, because z[4] = 3 = 7 - 4 and z[6] = 1 = 7 - 6. The answer is 2, which matches the borders a and aba.

Practice 2: The Z-array by hand

Compute the Z-array of abacaba by hand, one index at a time, using the window. Write down the window [l, r) after each index. Then run the program and compare.

Show the answer

Hint: index 4 is the one to check closely. When you reach it, the window is [2, 3) from index 2, so index 4 is outside it and you compare from the start. The Z-array is 7 0 1 0 3 0 1. At index 6 the window from index 4 is [4, 7), which is inside, so z[6] starts at min(1, z[2]) = 1, and the check confirms it.

Practice 3: The smallest period from the Z-array

A string has period p when s[i] == s[i+p] for every valid i. Its smallest period is the smallest p from 1 to n - 1 for which z[p] == n - p, or n when there is no such p. Use this to find the smallest period of aabaaab.

Show the answer

Hint: the Z-array of aabaaab is 7 1 0 2 3 1 0. Check p = 1, 2, 3, 4 in order. For p = 4 the value z[4] = 3 equals 7 - 4 = 3, and earlier values fail. The smallest period is 4. The same answer comes from the prefix function in the previous lesson, where the longest border of aabaaab is 3, so the period is 7 - 3 = 4.

Practice 4: Converting a Z-array into a prefix function

Given the Z-array 7 1 0 2 3 1 0 of aabaaab, use the conversion function to find the prefix function. Then explain why pi[6] is 3 by pointing to one entry of the Z-array.

Show the answer

Hint: the entry z[4] = 3 says that the suffix at 4 matches the prefix of length 3. So the prefix ending at position 4 + 2 = 6 has a border of length 3. The prefix function is 0 1 0 1 2 2 3, and pi[6] = 3 comes from z[4] = 3. The conversion function on this input gives the same array.

Practice 5: Prefix popularity by hand

For the string abacaba, compute how many positions match each prefix length k from 1 to 7. Then check your answer with the program.

Show the answer

Hint: each position i contributes to all k from 1 to z[i]. The Z-array is 7 0 1 0 3 0 1, so position 0 contributes to k = 1 through 7, position 2 to k = 1, position 4 to k = 1 through 3, and position 6 to k = 1. The counts are 4 2 2 1 1 1 1. For k = 4 only position 0 remains, since position 4 matches only three characters, so the count is 1.