The Longest Palindrome, Fast

Difficulty: 2000 6000 ms 128 MB

strings manacher

Print the length of the longest palindromic substring of S. |S| can be up to a million, so O(n²) center-expansion is too slow.

Input: one line with the string S.

Output: the longest palindromic substring length.

Constraints:

• 1 ≤ |S| ≤ 10⁶
• lowercase letters

Sample Tests

babad

3

cbbd

2

Read the Editorial