Note. In this note, we use zero-based indexing. That is, the first character of a string has index , and the last character has index .
The Z-function of a string at position is the length of the longest prefix of the substring starting at position that is also a prefix of the whole string .
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
More formally,
The value at position is usually defined as 0 or sometimes as the length of the string, depending on the convention.
A simple implementation checks the answer independently for each position.
For each index , we compare the substring starting at with the prefix of the string until we find the first mismatch or reach the end of the string.
This gives an solution.
To speed up the computation, we maintain the current Z-block.
A Z-block is a segment of the string that matches the prefix. We store its boundaries in two variables:
l — the left boundary;r — the right boundary.At any moment, [l, r) is the rightmost segment that matches a prefix of the string.
Initially:
l = 0r = 0Now suppose we want to compute z[i].
Then position i lies outside the current Z-block.
In this case, we compute z[i] naively by comparing characters starting from the prefix.
Then position i lies inside the current Z-block.
In this case, we already know that part of the answer can be reused. We look at the corresponding position inside the prefix:
and set
This gives a guaranteed correct lower bound. After that, we continue comparing characters naively if possible.
If the segment starting at i extends beyond the current r, we update the Z-block.
The total complexity of this algorithm is:
Given a text of length and a pattern of length , we want to find all occurrences of in .
We build a new string:
where # is a separator character that does not appear in either string.
Then we compute the Z-function of S.
For every position in the text, we look at:
If this value is equal to , then the pattern occurs in the text starting at position .
This gives an solution.
Given a string of length , find the shortest string such that is a concatenation of one or more copies of .
To solve this:
Then the string can be compressed to length .
This also works in linear time.
vector<int> z_function_slow(const string& s) {
int n = s.size();
vector<int> z(n);
for (int i = 1; i < n; i++) {
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
}
return z;
}
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; 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;
}