A slower O(nlog(n)) but IMO much simpler algorithm is to just using a rolling hash[1]. With linear time precomputation you can compute the hash of any substring

A slower O(nlog(n)) but IMO much simpler algorithm is to just using a rolling hash[1]. With linear time precomputation you can compute the hash of any substring range in constant time. Then for each position, you can just binary search for the longest palindrome centered at that position. [1]http://en.wikipedia.org/wiki/Rolling_hash http://en.wikipedia.org/wiki/Rolling_hash