Longest Palindromic Substring

You are given a string s. Your task is to find the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward. If there are multiple substrings of maximum length, output the one that appears first in the string.

Note: The solution must read from standard input (stdin) and write the result to standard output (stdout). The input consists of a single line, and the output should be exactly the longest palindromic substring.

Mathematical Notation:

If we denote the input string by \( s = s_0s_1\ldots s_{n-1} \), then a substring \( s[i..j] \) (where \( 0 \leq i \leq j

Your algorithm should efficiently identify the longest palindrome in the string.

inputFormat

The input is provided via stdin and contains a single line representing the string s.

Constraints: The string can be assumed to have a reasonable length for the algorithm to run in acceptable time.

outputFormat

Output the longest palindromic substring found in the input string. If there are multiple answers with the same maximum length, output the one that appears first in the string.

babad

bab