Browsing around a few days ago, I found a Ruby challenge site. Basically a “test your knowledge” type of deal. I’m always testing to see if I have any knowledge gaps, so I tried a few of the challenges (ok, more than a few, it was a weekend). One in particular has very little to do with Ruby, in fact, it’s a well known problem for all languages. Unlike most well known problems, this one has a well known solution that runs in O(n) time, and O(n) space. Manacher’s algorithm for finding the longest palindromic substring can be extended to return a list of all the palindromes in a particular string. I implemented this in Ruby. Gist here