Visualizing Manacher’s Algorithm

A commonly used algorithm question for interviews is finding the longest palindrome in a given string. It is a good question because there are so many ways to approach it. It is also a good question because many are surprised to learn that this can actually be done in linear time. The linear time algorithm, attributed to Manacher, is pretty mind boggling. I think this contributes to making the longest palindrome question good for interviews; even if you have seen Manacher’s approach beforehand, it is pretty hard to get an intuitive grasp on it. You would be hard pressed to regurgitate it back, like you might be able to do with other algorithms.

In an effort to get an intuitive grasp of how Manacher’s algorithm works, I have created a visualization using D3.js, which renders each step in the process of finding the longest palindrome. It is interactive and allows you to enter your own string to run through Manacher’s algorithm. I have to say I really didn’t understand the beauty of the algorithm until I made this visualization. I would like to do this in the future for other tricky algorithms and post them as computer science learning aids.

The visualization is hosted as a static site on AWS S3:

http://manacher-viz.s3-website-us-east-1.amazonaws.com/

Here’s what the finished result looks like: