Manacher's Algorithm

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

$$d(i)=\max \{j:i-j\ge 0\wedge i+j<n\wedge s_i{s}_{i-1}\dots s_{i-j}=s_i{s}_{i+1}\dots s_{i+j}\}$$

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 d(n, 0);
for (int i = 0; i < n; i++) {
	while (i - d[i] - 1 >= 0 && i + d[i] + 1 < n && s[i - d[i] - 1] == s[i + d[i] + 1]) {
		d[i]++;
	}
}
return d;

Algorithm 1

Lemma

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

Proof

$$\begin{array}{rl}{s}_j{s}_{j-1}\dots s_{j-d(j)}=s_j{s}_{j+1}\dots s_{j+d(j)}& ⟺s_{j-d(j)}{s}_{j-d(j)+1}\dots s_{j+d(j)}=s_{j+d(j)}{s}_{j+d(j)-1}\dots s_{j-d(j)}\\ & ⟹s_i{s}_{i-1}\dots s_{2i-j-d(j)}=s_{2j-i}{s}_{2j-i+1}\dots s_{3j+d(j)-2i}\wedge s_i{s}_{i+1}\dots s_{j+d(j)}=s_{2j-i}{s}_{2j-i-1}\dots s_{j-d(j)}\\ & ⟹d(i)\ge \min \{d(2j-i),j+d(j)-i\}\end{array}$$

Based on Algorithm 0, maintaining $\arg {\max }_{j=0}^{i-1}(j+d(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> d(n);
for (int i = 0, l = 0, r = 0; i < n; i++) {
	d[i] = i < r ? std::min(d[l + r - i - 1], r - i - 1) : 0;
	while (i - d[i] - 1 >= 0 && i + d[i] + 1 < n && s[i - d[i] - 1] == s[i + d[i] + 1]) {
		d[i]++;
	}
	if (i + d[i] + 1 > r) {
		l = i - d[i], r = i + d[i] + 1;
	}
}
return d;

Proof

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

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