Longest Palindromic Substring in O(N) (Manacher's Algorithm)

Finally, for an "interesting text" detector, the tool must find the longest stretch of a document that reads the same forwards and backwards, out of potentially a million characters. Given a string S, print the length of its longest palindromic SUBSTRING (contiguous, not subsequence). N can be up to 10^6, so an O(N^2) expand-around-center approach is too slow — implement Manacher's algorithm for O(N).

babad

3