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

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

std::vector<int> knuth_morris_pratt(int n, const std::string &s) {
	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

$$\sum _{i=2}^n(\pi (i-1)+1-\pi (i)+1)$$ $$\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}\}$, and let $a_j$ denote the $j$-th largest element in $S$.

Then, for each $j$ in $\{0,1,\dots ,|S|-2\}$, 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 to rule out some impossible $j$ yields an algorithm that solves the problem in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

std::vector<int> knuth_morris_pratt(int n, const std::string &s) {
	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;
}