Z Algorithm

The Z Algorithm is an algorithm that computes $z(0),z(1),\dots ,z(n-1)$ for a string $s$ of length $n$ in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space, where

$$z(i)=\mathrm{lcp}(s,s_i{s}_{i+1}\dots s_{n-1})$$

Algorithm 0

Applying the definition yields an algorithm that solves the problem in $\mathcal{O}(n^2)$ time and $\mathcal{O}(n)$ space.

std::vector z(n, 0);
for (int i = 0; i < n; i++) {
	while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
		z[i]++;
	}
}
return z;

Algorithm 1

Lemma

$$\forall j\in \{0,1,\dots ,n-1\},\forall i\in \{j,j+1,\dots ,n-1\},z(i)\ge \min \{z(i-j),j+z(j)-i\}$$

Proof

$$\begin{array}{rl}{s}_0{s}_1\dots s_{z(j)-1}=s_j{s}_{j+1}\dots s_{j+z(j)-1}& ⟹s_{i-j}{s}_{i-j+1}\dots s_{z(j)-1}=s_i{s}_{i+1}\dots s_{j+z(j)-1}\\ & ⟹z(i)\ge \min \{z(i-j),j+z(j)-i\}\end{array}$$

Based on Algorithm 0, maintaining $\arg {\max }_{j=1}^{i-1}(j+z(j))$ and applying the lemma yield an algorithm that solves the problem in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

std::vector<int> z(n);
z[0] = n;
for (int i = 1, l = 0, r = 0; i < n; i++) {
	z[i] = i < r ? std::min(z[i - l], r - i) : 0;
	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;

Proof

It is easy to prove that the upper bound of the total number of executions of z[i]++; is

$$\begin{array}{rl}\underset{i=1}{\overset{n-1}{\max }}(i+z(i))& \le n\\ & \in \mathcal{O}(n)\end{array}$$