uniolympiads Ελληνικά

Z-function

For each position ii, how many characters from ii agree with the start of the word. In O(n)O(n), with a "window" we already know.

When

The same as the prefix function: pattern search, periods, borders. Sometimes Z is more natural, e.g. when you ask "how long a common prefix does each suffix share with the whole word".

The idea

ziz_i is the length of the longest common prefix of ss and sisi+1…s_i s_{i+1} \dots By convention z0=0z_0 = 0.

Keep the window [l,r)[l, r) that ends furthest right among those found so far, with sl…sr−1=s0…sr−l−1s_l \dots s_{r-1} = s_0 \dots s_{r-l-1}. For i<ri < r, sis_i lies inside the window, so what we know about position i−li - l holds here as well, at most up to rr:

zi≥min⁡(r−i, zi−l).z_i \ge \min(r - i,\ z_{i-l}).

From there we continue comparing character by character. Every successful comparison beyond rr moves rr to the right, so the total is O(n)O(n).

Search. zz of p+#+tp + \texttt{\#} + t: an occurrence of pp at position jj of tt where z∣p∣+1+j=∣p∣z_{|p| + 1 + j} = |p|.

Pitfalls

  • z0z_0 is a convention. Some problems want z0=0z_0 = 0, others z0=nz_0 = n. Read the statement.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/z-function.cpp
// Z-function. z[i] = length of the longest common prefix of s and s[i..]; z[0] = 0 by convention.
// [l, r) is the rightmost window that matches a prefix; inside it z[i] starts from z[i - l]. O(n).

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0;
    int r = 0;
    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;
}

Tested on 3,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.