Illustration of the Manacher's Algorithm

I’ve noticed that most explanations of the Manacher’s Algorithm online tend to be overly focused on the details. This article focuses on the core principles, with the implementation details available in the code at the end.

What is the Manacher’s Algorithm?

Manacher’s Algorithm can find the longest palindromic substring of a string $s$ in $O(n)$ time.

If the sentence above👆🏻 doesn’t make much sense to you, you might want to check out this problem 👉🏻 Leetcode: Longest Palindromic Substring.

A simple $O(n^2)$ solution for finding the longest palindromic substring is easy to come up with: for each possible center, expand outwards symmetrically on both sides of the string $s$. This is known as the center expansion method.

Manacher’s Algorithm is essentially an optimization of the center expansion method.

How to Optimize It?

Let’s assume $s = cbcbccde$. We create an array $p$ where $p[i]$ represents the radius of the longest palindromic substring centered at $s[i]$. This may sound complex, but it will be clearer with an example in Figure 1.

Figure 1. Example: The longest palindrome centered at s[2] is “cbcbc”, with a radius of 3, so p[2] = 3.

The values of the $p$ array can be easily computed using the center expansion method, but doing so would result in a time complexity of $O(n^2)$. Manacher’s Algorithm leverages the information already known in $p$ to optimize the algorithm to $O(n)$.

Let’s illustrate this with an example: suppose $p[0]$, $p[1]$, and $p[2]$ are known, and we need to find $p[3]$, as shown in Figure 2.

Figure 2: With p[0] to p[2] known, we aim to determine p[3] using this information.

Now, let’s state a fact: the center of the longest palindromic substring with the farthest right boundary currently known is at $s[2]$, with its right boundary at $s[4]$. This is easy to understand by looking at Figure 3.

Figure 3: The red line represents the axis of symmetry, and s[4] is the current rightmost boundary known.

Once we accept this fact, the rest becomes straightforward. The value we need, $p[3]$, is at index 3, which falls within the range between center 2 and right boundary 4. By symmetry, $p[3] \geq p[2 - (3 - 2)] = p[1] = 2$. This is the essence of Manacher’s Algorithm: leveraging the symmetry property at this step. Here, $p[3] \geq p[2 - (3 - 2)]$ corresponds to $p[1]$, which is the point symmetric to $p[3]$ about the red axis shown in Figure 3.

Some Details

Why do we say $p[3] \ge p[1]$ instead of $p[3] = p[1]$? Let’s look at the example in Figure 4. In this case, it’s clear that the actual value of $p[3]$ is 3, which is greater than $p[1]$.

The reason is simple: the information we have is limited. Even though we make use of the known rightmost boundary, the true situation is that the right boundary of $p[3]$ extends beyond the current rightmost boundary.

To handle this, after calculating a value for $p[i]$ using the Manacher’s Algorithm (which may initially be less than the actual value), we simply expand around the center $s[i]$ using $p[i]$ as the starting radius, and keep updating $p[i]$ as we go. In the example shown in Figure 4, $i = 3$.

Figure 4: Note that, for clarity, the example has been slightly modified so that s[5] = b.

There is also a special case where calculating $p[i]$ using known information is only feasible when $i$ lies between the red symmetry axis and the corresponding right boundary in Figure 3. In all other cases, $p[i]$ can be computed directly using the center expansion method.

On Even-Length Palindromes

In the examples above, we focused only on odd-length palindromes (where the palindrome length is odd) to get straight to the core of the concept, leaving out even-length palindromes. The challenge with even-length palindromes is that their symmetry axis lies between two characters. However, there’s a simple trick to convert the problem of even-length palindromes into one involving only odd-length palindromes: insert a special character between every character in the string $s$. For example, convert $abac$ to $#a#b#a#c#$. This way, all even-length palindromes are transformed into odd-length ones, while odd-length palindromes remain unchanged.

Implementation in Golang

Here is the code for Leetcode: Longest Palindromic Substring.

func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func longestPalindrome(s string) string {
	ss := make([]byte, len(s)*2+1)
	ss[0] = '#'
	si := 1
	for i := 0; i < len(s); i++ {
		ss[si] = s[i]
		si++
		ss[si] = '#'
		si++
	}

	// Manacher's algorithm
	p := make([]int, len(ss))
	mid, maxRight := 0, 0
	maxPos := 0
	for i := 0; i < len(ss); i++ {
		if i < maxRight {
			p[i] = Min(p[2*mid-i], maxRight-i)
		} else {
			p[i] = 1
		}
		for i+p[i] < len(ss) && i-p[i] > -1 && ss[i+p[i]] == ss[i-p[i]] {
			p[i]++
		}
		if i+p[i] > maxRight {
			mid = i
			maxRight = i + p[i]
		}
	}
	for i := 0; i < len(p); i++ {
		if p[i] > p[maxPos] {
			maxPos = i
		}
	}
	return s[(maxPos-p[maxPos]+1)/2 : (maxPos+p[maxPos]-1)/2]
}

This article is licensed under CC BY-NC-SA 4.0, please cite if you intend to reproduce.