Manacher Palindromes 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 Palindromes source code, pseudocode and analysis