{"id":"4d042587-3fa1-4d0e-8a42-a534477b2c0c","name":"Manacher's Algorithm","description":"1. You are given one string s1.\r\n2. You have to find the longest palindromic substring in s1.\r\n3. Expected Complexity : O(n)","inputFormat":"one string s1","outputFormat":"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","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void solution(String s1) {\r\n // write your code here\r\n\r\n }\r\n \r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n String s1 = scn.next();\r\n solution(s1);\r\n System.out.println();\r\n\t}\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abadxd","sampleOutput":"3\r\naba","questionVideo":"https://www.youtube.com/embed/06QIlUBLTz4","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","slug":"manacher-s-algorithm","type":1}],"next":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"},"prev":{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","type":1,"slug":"find-string-roots"}}}

Manacher's Algorithm

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

{"id":"4d042587-3fa1-4d0e-8a42-a534477b2c0c","name":"Manacher's Algorithm","description":"1. You are given one string s1.\r\n2. You have to find the longest palindromic substring in s1.\r\n3. Expected Complexity : O(n)","inputFormat":"one string s1","outputFormat":"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","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void solution(String s1) {\r\n // write your code here\r\n\r\n }\r\n \r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n String s1 = scn.next();\r\n solution(s1);\r\n System.out.println();\r\n\t}\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abadxd","sampleOutput":"3\r\naba","questionVideo":"https://www.youtube.com/embed/06QIlUBLTz4","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","slug":"manacher-s-algorithm","type":1}],"next":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"},"prev":{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","type":1,"slug":"find-string-roots"}}}
plane

Editor

Loading...

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

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode