Longest palindromic substring

The naive approach, iterating over all substrings and checking whether they are palidromic, runs in $O(n^3)$ time.

A better approach is to iterate over all characters and determine the longest palindrome centered at each character by expanding outward. This runs in $O(n^2)$ time.

However, a small change makes the above approach run in linear time. It's called Manacher's algorithm. The idea is to maintain an array of the longest palindrome centered