Manacher's Algorithm

hard
Question Solve Solutions 
1. You are given one string s1.
2. You have to find the longest palindromic substring in s1.
3. Expected Complexity : O(n)

Input Format

one string s1

Output Format

Print the length of the longest palindrome substring in the first line. In the second line print the longest palindromic substring in s1. If there is more than one palindromic substring with the maximum length, output the first one.

Constraints

1 <= length of the string <= 10^5

Example

Input
abadxd
Output
3
aba
Previous
Find String Roots
Next
String Rotation

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Kmp Pattern Searching hard Z Algorithm For Pattern Searching hard Find String Roots hard String Rotation hard Prefix And Suffix Count medium Say No To Palindrome medium String Polynomial Hashing medium Diane medium Rabin Karp Pattern Find (spoj) hard Password medium Good Substrings hard Longest Duplicate Substring medium Longest Prefix Suffix hard Lexicographical Suffixes