Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same backwards as forwards. To solve this problem, you may consider expanding around each character (and between characters) to find palindromic substrings. The expansion technique can be described by the formula: $$s[i\ldots j]$$ is a palindrome if $$s[i]=s[j]$$ and $$s[i+1\ldots j-1]$$ is a palindrome.

Print the result in the format: The longest palindromic substring is: X, where X is the longest palindromic substring found in the given string.

inputFormat

The input consists of a single line containing a non-empty string s.

You should read the input from stdin.

outputFormat

Output a single line: the string The longest palindromic substring is: X where X is the longest palindromic substring in the input string computed by your program. The output should be written to stdout.

babad

The longest palindromic substring is: bab