Discovered an interesting algorithm for finding longest palindrome by playing with sequences in a text editor. Anyone know if there's a name for this algorithm?
Worst running time is O(n^2), which is better than the naive implementation of O(n^3) but not as efficient as some O(n) implementations (http://www.akalin.cx/longest-palindrome-linear-time). In general, assuming a non-pathological case, running time is around 2n * m where n is the length of the string and m is the mean length of all palindromes. For non-pathological cases (i.e. human sentences), n is often logarithmic (log n) and fast approaches 1 as n increases. This puts the average case complexity at around n log n and best-case n.
Developed as a solution to: http://www.therubygame.com/challenges/4
Original hand-work to discover a pattern: