Z-function
Note. This article uses -based indices, i.e., the first character of the string has index , and the last has .
The Z-function of a string at position is the length of the longest prefix of the substring starting at position that matches the prefix of the entire string .
Formally:
The value is usually taken to be or by convention.
There is a simple implementation with complexity , where is the length of the string.
For each position we increase while the characters match.
We will call a Z-block a substring of the string starting at position and having length , i.e., matching the prefix of the string.
For the algorithm we introduce two variables:
Initially:
Assume that the values of are already known for positions .
Find .
The position is outside the current Z-block.
Compare characters directly:
while they match.
Let the first mismatching index be . Then:
Update the boundaries:
The position is inside the current Z-block.
Consider the symmetric position:
Then it is known:
After expansion we update:
Linear implementation :
Given strings:
It is required to find all occurrences of in .
Construct the string:
where the character is a separator that does not occur in and .
Compute the Z-function of the string .
For each position in the text :
If:
then an occurrence of starts at position of the string .
Otherwise — no.
Asymptotics:
Given a string of length .
Find the shortest string such that:
(one or more copies of ).
Compute the Z-function of the string and iterate over all divisors of the number .
If the following holds:
then the string has period , and it can be compressed to length .
Take the minimal such .
Asymptotics:
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);
int l = 0, 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;
}