Longest Palindrome by Concatenating a Prefix and a Suffix

Given a string \(S\), you are allowed to choose one prefix of \(S\) and one suffix of \(S\> (each may be chosen independently) and then concatenate them in order (i.e. prefix first, then suffix) to form a new string \(T = P+Q\). The twist is that you are not free to choose arbitrary \(P\) and \(Q\); they must come from the beginning and the end of \(S\), respectively.

Find a way to obtain a palindrome \(T\) with maximum length. It turns out that the answer can be computed by taking the maximum between the length of the longest palindromic prefix of \(S\) and the longest palindromic suffix of \(S\) (denote it as \(L\)). Then, if \(L>1\) the answer is \(2L\) (by using the chosen palindromic part from one end and duplicating it as the other piece), and if no non‐trivial palindromic prefix or suffix exists (i.e. \(L=1\)), the answer is \(1\>.

More formally:

• Let \(L_p\) be the maximum length such that \(S[0 \ldots L_p-1]\) is a palindrome.
• Let \(L_s\) be the maximum length such that \(S[len(S)-L_s \ldots len(S)-1]\) is a palindrome.
• Let \(L = \max(L_p, L_s)\). The answer is defined as:

[ \text{answer} = \begin{cases} 2L, & \text{if } L > 1,\ 1, & \text{if } L = 1. \end{cases} ]

For example:

• For \(S=\texttt{aba}\): the longest palindromic prefix is \(\texttt{aba}\) (length 3) and the longest palindromic suffix is also \(\texttt{aba}\) (length 3). Hence, the answer is \(2\times3=6\).
• For \(S=\texttt{abb}\): the longest palindromic prefix is \(\texttt{a}\) (length 1) while the longest palindromic suffix is \(\texttt{bb}\) (length 2). Thus, the answer is \(2\times2=4\).
• For \(S=\texttt{abc}\): the longest palindromic prefix is \(\texttt{a}\) (length 1) and the longest palindromic suffix is \(\texttt{c}\) (length 1), so the answer is 1.

inputFormat

The input consists of a single line, which is the string \(S\). \(S\) will contain only lowercase letters.

outputFormat

Output a single integer, which is the maximum length of a palindrome that can be obtained by concatenating a prefix and a suffix of \(S\), according to the rule described above.

sample

aba

6