Manacher's algorithm is a very handy algorithm with a short implementation that can make many programming tasks, such as finding the number of palindromic substrings or finding the longest palindromic substring, very easy and efficient. The running time of Manacher's algorithm is O(N) where N is the length of the input string.