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 to find $z$ yields an algorithm that solves the problem in $\mathcal{O}(n^2)$ time and $\mathcal{O}(n)$ space.

std::vector<int> z(int n, const std::string &s) {
	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 to get a lower bound for $z(i)$ yield an algorithm that solves the problem in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

std::vector<int> z(int n, const std::string &s) {
	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 on the total number of executions of z[i]++ is

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