$Z$-function of a given string $S$ is an array of integers, where $i$-th element equals to the length of longest prefix of $S$ which is, in the same time, is prefix of $S$'s suffix starting at $i$:
\[Z[i] = \max k \mid S[i\, \ldots \, i + k] = S[0 \ldots k]\]
Naive algorithm for computing $Z$-function finds the length of the substring starting at position in the string which matches some prefix of $S$:
std::vector NaiveZ(std::string s) {
const int n = s.length();
std::vector z;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && s[j] == s[j - i]) j++;
z.push_back(j - i);
}
return z;
}
To find $Z$-function in linear time one can use a notation of $Z$-block — a substring of $S$ matching some prefix of $S$. Lets keep positions of the beginning and the end of $Z$-block in variables $L$ and $R$. If already calculated value of $Z$-function at position $i-L$ is less than $R-i$, then we may reuse this value and just copy it to $Z[i]$. Otherwise we need to move $L$ to $i$ and expand $R$ as much as possible:
std::vector Z(std::string s) {
const int n = s.length();
std::vector z(n);
z[0] = n;
int L = 0;
int R = 0;
for (int i = 1; i < n; i++) {
if (z[i - L] < R - i) {
z[i] = z[i - L];
continue;
}
R = std::max(i, R);
L = i;
while (R < n && s[R - L] == s[R]) R++;
z[i] = R - i;
}
return z;
}