Manacher Algorithm Visualized

Longest Palindromic Substring in O(n)

One of the most beautiful algorithms in computer science, the one that demonstrates how it is possible to gain a tremendous speedup from the sluggish O(n³) to the blazing fast¹ O(n) by just looking at the problem from a different perspective.

The task is to find the longest substring that happens to be a palindrome (=reads the same way right-to-left and left-to-right, eg ‘racecar’). For example, the longest palindrome in ‘Fractions are never odd or even’ is ‘never odd or even’, (letter case and spaces are ignored). It has practical applications in biochemistry (GAATTC and CTTAAG are called palindromic sequences²). It is a typical interview task³.

The most straightforward approach (and the slowest one at the same time) is to iterate over all starts and lengths, checking if the corresponding substring is a palindrome:

The pseudocode

loop over substring start:
__loop over substring length:
____loop over letters in substring

clearly indicates that it is a O(n³) method (where n is the length of the text), which is a rapidly growing function.

If instead of looping over the starts, we loop over the middles, we will be able to re-use the results of the previous steps.

For example, if we know that ‘eve’ is a palindrome, it will take us just one more comparison to figure out that ‘level’ is a palindrome, too. In the first method we’d have to rerun the entire check from scratch.

loop over substring middle
__loop over substring length

This one is O(n²). But there are methods⁴ that allow doing it even faster.

One of the most elegant is the Manacher algorithm⁵. It is based on the O(n²) method described above, but the heuristics it introduces cuts down time complexity to O(n).

When the palindromes in the text are far apart, there’s nothing to optimize here. It is O(n) already. The problem arises when they overlap, with the worst case being a text made from a single letter.

Consider the following situation. The algorithm found the shorter green palindrome, the longer blue palindrome, and stopped at the letter ‘i’: