Today I just learned a new amazing algorithm. It’s called Manacher’s algorithm, the algorithm that finds the longest palindromic substring in linear time. Previously, I never thought that it can be done faster than O(N^2) time complexity (by dynamic programming). I felt really impressive after reading this blog and knew that this algorithm was found in 1975 :) So I wanna share it HERE.