It’s a 3-day weekend here in the US of A, so what better way to spend it than learning about new and exciting data structures?

(Rhetorical question!)

A naïve way to find the longest palindromic substring of an input string is to start from every possible center-of-a-palindrome and work outwards, adding the next letter from each side until those letters aren’t equal. The center could either be a letter, or it could be in between 2 letters - so for string of length n there will be 2n + 1 centers. This makes our naïve approach O(n^2). Not a terrible first stab, but we can do better.

Palindrome Trees do this in O(n) (technically quasilinear, but we dutifully ignore constants with big O notation). They’re not the first algorithm to do so - Manacher’s Algorithm1 is from 1975 - but they’re proposed as an improvement with smaller space usage.

What’s neat about Palindrome Trees is that they’re super new - the paper just came out in 2015, and I could only find a handful of blogs about them (between Geeks for Geeks post and Adilet’s post it was pretty easy to get up to speed, but I appreciated Alessio’s post for pointing me to the academic paper2). I saw a number of C/++ versions, and Alessio’s Java solution, so I thought I’d try my hand at a python one, just for fun.

The code’s up in my first ever gist, but this also seemed like a good excuse to add syntax highlighting to this website (via Rouge), so in celebration:

1. Not to imply that I’m super familiar with Manacher’s, just aware of its existence.

2. I didn’t read the full 21 pages 🤷‍♀️