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$, where

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

in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

Tip

This problem can also be solved by Kasai’s Algorithm in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space.

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 i\in \{0,1,\dots ,n-1\},\forall j\in \{1,2,\dots ,i-1\},i<j+z(j)\Rightarrow 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 find 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, j = -1; i < n; i++) {
		z[i] = ~j && i < j + z[j] ? std::min(z[i - j], j + z[j] - i) : 0;
		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
			z[i]++;
		}
		if (j == -1 || j + z[j] < i + z[i]) {
			j = i;
		}
	}
	return z;
}

Proof

It is easy to prove that the total number of executions of z[i]++ is bounded by

$$\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}$$