Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt Algorithm is an algorithm that computes $\pi (1),\pi (2),\dots ,\pi (n)$ for a string $s$ of length $n$ in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space, where

$$\pi (i)=\max \{j:j<i\wedge s_0{s}_1\dots s_{j-1}=s_{i-j}{s}_{i-j+1}\dots s_{i-1}\}$$

Algorithm 0

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

std::vector pi(n + 1, 0);
for (int i = 2; i <= n; i++) {
	for (int j = i - 1; j > 0; j--) {
		if (s.substr(0, j) == s.substr(i - j, j)) {
			pi[i] = j;
			break;
		}
	}
}
return pi;

Algorithm 1

Lemma

$$\forall i\in \{2,3,\dots ,n\},\pi (i)\le \pi (i-1)+1$$

Proof

$$\begin{array}{rl}\pi (i)=j& ⟹s_0{s}_1\dots s_{j-1}=s_{i-j}{s}_{i-j+1}\dots s_{i-1}\\ & ⟹s_0{s}_1\dots s_{j-2}=s_{i-j}{s}_{i-j+1}\dots s_{i-2}\\ & ⟹\pi (i-1)\ge j-1\end{array}$$

Based on Algorithm 0, applying the lemma yields an algorithm that solves the problem in $\mathcal{O}(n^2)$ time and $\mathcal{O}(n)$ space.

std::vector pi(n + 1, 0);
for (int i = 2; i <= n; i++) {
	for (int j = pi[i - 1] + 1; j > 0; j--) {
		if (s.substr(0, j) == s.substr(i - j, j)) {
			pi[i] = j;
			break;
		}
	}
}
return pi;

Proof

The total number of executions of s.substr(0, j) == s.substr(i - j, j) is

$$\begin{array}{rl}\sum _{i=2}^n(\pi (i-1)+1-\pi (i)+1)& =\pi (1)-\pi (n)+2(n-1)\\ & \le 2n\\ & \in \mathcal{O}(n)\end{array}$$

Algorithm 2

Lemma

Let $\pi (0)=0$, then

$$\{j:j<i\wedge s_0{s}_1\dots s_{j-1}=s_{i-j}{s}_{i-j+1}\dots s_{i-1}\}=\{\pi (i),\pi (\pi (i)),\pi (\pi (\pi (i))),\dots \}$$

Proof

Let $S=$ $\{j:j<i\wedge s_0{s}_1\dots s_{j-1}=s_{i-j}{s}_{i-j+1}\dots s_{i-1}\}$, $a_j$ denote the $j$-th largest element in $S$. Then for $j\in \{1,2,\dots ,|S|-1\}$, since

$$s_0{s}_1\dots s_{a_j-1}=s_{i-a_j}{s}_{i-a_j+1}\dots s_{i-1}⟹\forall k\in \{0,1,\dots ,a_j-1\},s_{a_j-k}{s}_{a_j-k+1}\dots s_{a_j-1}=s_{i-k}{s}_{i-k+1}\dots s_{i-1}$$

it follows that

$$\begin{array}{rl}{a}_{j+1}& =\max \{k:k<a_j\wedge s_0{s}_1\dots s_{k-1}=s_{i-k}{s}_{i-k+1}\dots s_{i-1}\}\\ & =\max \{k:k<a_j\wedge s_0{s}_1\dots s_{k-1}=s_{a_j-k}{s}_{a_j-k+1}\dots s_{a_j-1}\}\\ & =\pi (a_j)\end{array}$$

Based on Algorithm 1, applying the lemma yields an algorithm that solves the problem in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

std::vector<int> pi(n + 1);
pi[0] = pi[1] = 0;
for (int i = 1, j = 0; i < n; i++) {
	while (j && s[j] != s[i]) {
		j = pi[j];
	}
	j += s[j] == s[i];
	pi[i + 1] = j;
}
return pi;