Manacher's Algorithm
hard
1. You are given one string s1. 2. You have to find the longest palindromic substring in s1. 3. Expected Complexity : O(n)
Constraints
1 <= length of the string <= 10^5
Format
Input
one string s1
Output
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.
Example
Sample Input
abadxd
Sample Output
3
aba
Question Video