题目描述

给定一个字符串 $S$，请找出 $S$ 的一个前缀和后缀，使得它们拼接后是一个回文串。请输出这个串的最长长度。

输入格式

输入一行包含一个字符串 $S$，由小写英文字母组成。

输出格式

输出一行包含一个整数表示答案。

aababa

7

提示

样例说明

选择前缀 $\tt{aababa}$ 和后缀 $\tt{a}$ 可以得到 $\tt{aababaa}$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例， $|S| \leq 300$；
• 对于 $60\%$ 的评测用例， $|S| \leq 3000$；
• 对于所有评测用例， $1 \leq |S| \leq 10^5$。