P4287 [SHOI2011] Double Palindrome

Let the reversal of a string $w$ be denoted by $w^{\mathsf R}$. For example, $\tt (abcd)^{\mathsf R}=dcba$, $\tt (abba)^{\mathsf R}=abba$. For a string $x$, if $x$ satisfies $x^{\mathsf R}=x$, it is called a palindrome. For example, $\tt abba$ is a palindrome, while $\tt abed$ is not. If $x$ can be written in the form $ww^{\mathsf R} ww^{\mathsf R}$, it is called a "double palindrome". In other words, for $x$ to be a double palindrome, the length of $x$ must be a multiple of $4$, and $x$, its first half, and its second half must all be palindromes. For example, $\tt abbaabba$ is a double palindrome, while $\tt abaaba$ is not, because its length is not a multiple of $4$. - A substring of $x$ is a string formed by a consecutive segment of characters in $x$. For example, $\tt be$ is a substring of $\tt abed$, while $\tt ac$ is not. - A palindromic substring of $x$ is a substring of $x$ that is a palindrome. - A double palindromic substring of $x$ is a substring of $x$ that is a double palindrome. Your task is to compute the length of the longest double palindromic substring of the given string.

The input consists of two lines. - The first line contains an integer $N$, the length of the string. - The second line contains a string of lowercase English letters, which is the content of the string.

Output a single line: the length of the longest double palindromic substring of the input string. If no double palindromic substring exists, output $0$.

Constraints For all testdata, $1 \le N \le 500000$. Translated by ChatGPT 5