manacher Algorithm

Therefore, it provides a linear time solution to the longest palindromic substring problem. However, as detected e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in linear time.

manacher source code, pseudocode and analysis