Manacher's Algorithm

Manacher's algorithm finds the longest palindromic substring of a string in linear time by processing the string from left to right while maintaining the boundaries of the rightmost palindrome found so far, and using the already-known palindrome lengths of positions mirrored within that rightmost palindrome to avoid recomputing information a previous step has already established, only extending a palindrome check character by character when the mirrored information runs out. This improves on the naive approach of checking every possible center for a palindrome, which takes O(n squared) time in the worst case. Glenn Manacher published the technique in 1975.