Friday, August 28, 2015

Longest Subpalindrome in Linear Time

I've finally rewritten the linear time algorithm for finding the longest palindromic substring ("subpalindrome") within a given string. I originally came across this problem in Peter Norvig's class on Udacity and have worked on it quite a bit since then.

I'm not altogether satisfied with the clarity of the code -- it is quite imperative and stateful, with many indexing variables -- but I don't see a way to meaningfully refactor without changing the fundamental structure, so I'll leave that for another day.

Algorithm Description and Visualization