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

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

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

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