Longest Palindromic Substring (Manacher's Algorithm)

Longest Palindromic Substring Given a string s containing printable ASCII characters, output its longest contiguous palindromic substring. A palindrome reads the same forward and backward. For example, "aba" and "aaaa" are palindromes. If multiple longest palindromic substrings exist, output the one with the smallest starting index. Your algorithm must run in O(n) time, where n = len(s). Input Format One line containing the string s. Output Format Print the longest palindromic substring of s. Constraints 1 <= len(s) <= 2 * 10^5 s contains no newline characters. Example Input: babad Output: bab Both "bab" and "aba" are longest palindromic substrings. "bab" is printed because it starts earlier. Example Input babad Output bab