Z-function
For each position , how many characters from agree with the start of the word. In , 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
is the length of the longest common prefix of and By convention .
Keep the window that ends furthest right among those found so far, with . For , lies inside the window, so what we know about position holds here as well, at most up to :
From there we continue comparing character by character. Every successful comparison beyond moves to the right, so the total is .
Search. of : an occurrence of at position of where .
Pitfalls
- is a convention. Some problems want , others . Read the statement.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// 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.
- String Matching · String Algorithms
- String Functions · String Algorithms
More in the USACO Guide
- String Searching · usaco.guide/adv/string-search
In English, with more problems per level.